bfs

http://poj.org/problem?id=3278

//poj3278
//在n的位置上,抓到k的位置上的牛，牛不动，需要几步，记录过程
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define ph push
#define all(x) (x).begin(), (x).end()
int n,k;
const int N=100006;
struct step{
    int x;
    int steps;
    step(int xx,int s):x(xx),steps(s){}
};
queue<step> q;
int vis[N];
bool f(int x){
    return x>=0&&x<N;
}
void bfs(){
    while(!q.empty()){
        step s=q.front();
        if(s.x==k){
            cout<<s.steps<<endl;
            return ;
        }
        if(f(s.x-1)&&!vis[s.x-1]){
            q.ph(step(s.x-1,s.steps+1));
            vis[s.x-1]=1;
        }
        if(f(s.x+1)&&!vis[s.x+1]){
            q.ph(step(s.x+1,s.steps+1));
            vis[s.x+1]=1;
        }
        if(f((s.x)<<1)&&!vis[(s.x)<<1]){
            q.ph(step((s.x)<<1,s.steps+1));
            vis[(s.x)<<1]=1;
        }
        q.pop();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    memset(vis,0,sizeof(vis));
    q.ph(step(n,0));
    bfs();
}

http://poj.org/problem?id=3984

//poj3984
//一个5*5的迷宫，1代表墙，0代表路 [1][1]->[5][5]最短
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define ph push
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int INF = 1e10;
struct nod {
    int x, y;
    int father;
    nod(int xx = 0, int yy = 0, int f = 0) : x(xx), y(yy), father(f) {}
};
int mi[8][8];
nod q[200];
int head, tail;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void bfs() {
    while (head != tail) {
        nod nd = q[head];
        if (nd.x == 5 && nd.y == 5) {
            vector<nod> temp;
            while (true) {
                temp.pb(nod(nd.x, nd.y, 0));
                if (nd.father == -1) {
                    break;
                }
                nd = q[nd.father];
            }
            for (int i = temp.size() - 1; i >= 0; --i) {
                cout << "(" << temp[i].x - 1 << ", " << temp[i].y - 1 << ")" << endl;
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            int x = nd.x + dx[i], y = nd.y + dy[i];
            if (!mi[x][y]) {
                q[tail++] = nod(x, y, head);
                mi[x][y] = 1;
            }
        }
        ++head;
    }
}
int main() {
    ios::sync_with_stdio(false);
    memset(mi, INF, sizeof(mi));
    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 5; j++) {
            cin >> mi[i][j];
        }
    }
    head = 0;
    tail = 1;
    q[0] = nod(1, 1, -1);
    bfs();
}

https://www.luogu.org/problemnew/show/P1443

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define ph push
#define pb push_back
#define all(x) (x).begin(), (x).end()
int n,m,a,b;
int ma[405][405];
queue<pair<pair<int,int>,int> > q;
bool tf(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}
int dx[]={-2,-2,2,2,-1,-1,1,1};
int dy[]={1,-1,1,-1,2,-2,2,-2};
void bfs(){
    while(!q.empty()){
        pair<pair<int,int>,int> p=q.front();
        for(int i=0;i<8;++i){
            int x=p.ff.ff+dx[i],y=p.ff.ss+dy[i];
            if(tf(x,y)&&ma[x][y]==-1){
                q.ph(mp(mp(x,y),p.ss+1));
                ma[x][y]=p.ss+1;
            }
        }
        q.pop();
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            printf("%-5d",ma[i][j]);
        }
        cout<<endl;
    }
}
int main() {
//    ios::sync_with_stdio(false);
    cin>>n>>m>>a>>b;
    memset(ma,-1,sizeof(ma));
    q.ph(mp(mp(a,b),0));
    ma[a][b]=0;
    bfs();
    return 0;
}