专题地址：https://vjudge.net/contest/65959#overview

• BFS模板

typedef struct node {
    int x,y;
    int time;
};

int bfs(node s) {
    queue<node> Q;  //创建队列
    node now,next;  //now next结点
    Q.push(s);      //加入开始头节点
    vis[s.x][s.y]=1;    //头节点访问

    while(!Q.empty()) {
        now = Q.front();
        Q.pop();

        for(int i=0; i<4; i++) {
            if(pass(now))   //当前结点满足条件
                return now.time;//返回结点值

            //当前结点不满足条件 宽度搜索
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            next.time=now.time;

            if(check(next)) {   //坐标未越界 未访问过
                next.time+=1;   //路程加一
                vis[next.x][next.y]=1;  //访问加一
                Q.push(next);       //加入队尾
            }
        }
        return -1;
    }

A - 棋盘问题 POJ - 1321

• 按行向下搜索 简单DFS

#include<iostream>
#include<string.h>
#define maxn 20

using namespace std;
char map[maxn][maxn];
int vis[maxn];
int n,k;
int cnt,result;
int dfs(int x) {


    /*
    int dir[4][2] = {(-1,0),(1,0),(0,-1),(0,1)};
    for(int i=0;i<4;i++){
        int nx=dir[i][0]+x;
        int ny=dir[i][1]+y;
    */

    if(x>n)
        return result;
    if(cnt==k) {
        result++;
        return 0;

    }
    for(int i=0; i<n; i++) {
        if(map[x][i]=='#'&&vis[x]==0) {

            vis[x]=1;
            cnt++;
            dfs(x+1);
            cnt--;
            vis[x]=0;
        }
    }


    //不满足则到下一行
    dfs(x+1);

}
int main() {
    while(scanf("%d %d",&n,&k)) {
        if(n==-1&&k==-1)
            break;

        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++) {
            scanf("%s",map[i]);
        }

        result=0;
        cnt=0;

        cout<<dfs(0)<<endl;
    }
    return 0;
}

B - Dungeon Master POJ - 2251

• 三层BFS 队列

#include<iostream>
#include<string.h>
#include<queue>
#define maxn 30+5
using namespace std;

typedef struct pnode {
    int x,y,z;
    int minute;
} pnode ;

char map[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
int dir[6][3]= {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int L,R,C;
pnode sp;
pnode ep;

int check(int x,int y,int z) {
 
        if(x<0 || y<0 || z<0 || x>=L || y>=R || z>=C)
            return -1;
        else if(map[x][y][z] == '#')
            return -1;
        else if(vis[x][y][z])
            return -1;
        return 1;
        
        //写反条件 
    
}
void display(pnode p) {
    cout<<p.x<<" ";
    cout<<p.y<<" ";
    cout<<p.z<<endl;
}
int bfs(pnode s) {

    queue<pnode> Q;
    pnode now,next;
    Q.push(s);
    vis[s.x][s.y][s.z]=1;
    while(!Q.empty()) {
        now = Q.front();
        //cout<<now.minute<<"队列循环+"<<endl;;
        Q.pop();

        //出bfs条件
        if(now.x==ep.x&&now.y==ep.y&&now.z==ep.z) {
            return now.minute;
        }

        for(int i=0; i<6; i++) {
            next.x=0;
            next.y=0;
            next.z=0;
            next.minute=0;

            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];
            next.z = now.z+dir[i][2];


            if(check(next.x,next.y,next.z)==1) {
                //cout<<"checked"<<endl;
                vis[next.x][next.y][next.z] = 1;
                next.minute = now.minute+1;
                Q.push(next);
            }
        }
    }
    return -1;
}



int main() {
    while(scanf("%d %d %d",&L,&R,&C)) {
        if(L==0||R==0||C==0)
            break;
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        for(int i=0; i<L; i++)
            for(int j=0; j<R; j++)
                for(int k=0; k<C; k++) {

                    char ct;
                    cin>>ct;
                    if(ct=='S') {

                        sp.x=i;
                        sp.y=j;
                        sp.z=k;
                        sp.minute=0;
                    }
                    if(ct=='E') {

                        ep.x=i;
                        ep.y=j;
                        ep.z=k;
                        ep.minute=0;
                    }
                    map[i][j][k] = ct;
                }

        int result = bfs(sp);
        if(result==-1)
            cout<<"Trapped!"<<endl;
        else
            printf("Escaped in %d minute(s).\n",result);
    }


    return 0;
}

C - Catch That Cow POJ - 3278

• 一维数组 三方向BFS

#include<iostream>
#include<string.h>
#include<queue>
#define maxn 100000+5

using namespace std;
int N,K;
int map[maxn];
int vis[maxn];
typedef struct node {
    int time;
    int x;
} node;

int walkThisTime;
int mintime = 0xFFFFFF;

int jump(int x,int choice) {
    if(choice==0)
        return x+1;
    if(choice==1)
        return x-1; 
    if(choice==2)
        return 2*x;
    
}

int check(int x) {
    if(x<0||x>maxn)
        return -1;
    else if(vis[x]==1)
        return -1;
    else
        return 1;
}

//三方向bfs
int bfs(node s) {
    queue<node> Q;
    node now,next;
    Q.push(s);
    vis[s.x]=1;
    
    while(!Q.empty()) {
        now = Q.front();
        Q.pop();

        for(int i=0; i<3; i++) {
            int walkThisTime = jump(now.x,i);
            next.x = now.x;
            next.time = now.time;
            /* 
            cout<<"当前坐标"<<next.x<<endl;
            cout<<"当前步数"<<next.time<<endl;
            cout<<"下一步坐标："<<walkThisTime<<endl;
            cout<<endl;
            */ 
            next.x = walkThisTime;
    
            if(check(next.x)==1) {
                vis[next.x]=1;
                next.time+=1;
                Q.push(next);
            }
            
            if(next.x==K)return next.time;
        }
    }
    return -1;
}


int main() {
    scanf("%d %d",&N,&K);
    memset(map,0,sizeof(map));
    node s;
    s.time=0;
    s.x=N;

    if(N>=K) {
        cout<<N-K<<endl;
    } else {
        cout<<bfs(s)<<endl;
    }

    return 0;
}