Catch the catは幅探索法BFSを用いる
1176 ワード
1.一般的な幅優先検索;
2.典型的なキュー使用問題;
3.最初はWAでしたが、境界を間違えていました.覚えておいてください.境界を越えるとwaです.
コードは次のとおりです.
2.典型的なキュー使用問題;
3.最初はWAでしたが、境界を間違えていました.覚えておいてください.境界を越えるとwaです.
コードは次のとおりです.
#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>
using namespace std;
int step[100010], flag[100010];
queue <int> q;
void bfs(int n, int k)
{
q.push(n);
flag[n] = 1;
while(q.size())
{
int x = q.front();
q.pop();
if(k == x) break;
if(x -1 >= 0 && !flag[x - 1])
{
step[x - 1] = step[x] + 1;
q.push(x - 1);
flag[x - 1] = 1;
}
if(x + 1 <= 100000 && !flag[x + 1])
{
step[x + 1] = step[x] + 1;
q.push(x + 1);
flag[x + 1] = 1;
}
if(x * 2 <= 100000 && !flag[x * 2])
{
step[x * 2] = step[x] + 1;
q.push(x * 2);
flag[x * 2] = 1;
}
}
}
int main()
{
int N, K;
cin >> N >> K;
memset(flag, 0,sizeof(flag));
memset(step, 0,sizeof(step));
bfs(N, K);
cout << step[K] <<endl;
return 0;
}