Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <queue> #include <cstring> using namespace std; vector<int> possible_operations(int node) { vector<int> moves; moves.push_back(node*2); moves.push_back(node*3); moves.push_back(node+1); return moves; } int BFS(int N, int R) { queue<int> queue; int operations[R + 1]; memset(operations, 127, sizeof(operations)); //nekoj golem broj queue.push(N); operations[N] = 0; //trebaat 0 operacii za da se stigne do N (pochetok) while (!queue.empty()) { auto node = queue.front(); queue.pop(); if (node == R) { //go najdovme odgovorot break; } vector<int> moves = possible_operations(node); for (auto next : moves) { if (next <= R) //ne razgleduvame broevi pogolemi od R { if (operations[next] > operations[node] + 1) { //mozhe da odime od node do next so 1 operacija operations[next] = operations[node] + 1; queue.push(next); } } } } return operations[R]; } int main() { int N, R; cout << "Please enter N and R (make sure R>N): " << endl; cin >> N >> R; int minOperations = BFS(N, R); cout << minOperations << endl; return 0; }
Input data
Program output
10 63
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!