BFS

搜索算法有很多，其中最主要也是最重要的两个就是宽度优先遍历（BFS）和深度优先遍历（DFS），其它如A*之类的很多搜索算法都是他们的延伸。

BFS模版（红黑瓷砖问题）：

#include<bits/stdc++.h>
using namespace std;
int move_x[] = {-1,0,1,0};
int move_y[] = {0,-1,0,1};
 
char a[51][51];
int ans,w,h;
struct node{
	int x,y;
};
void BFS(int Wx,int Wh){
    ans = 1;
    queue <node> q;
    node start, next;
    start.x = Wx;
    start.y = Wh;
    q.push(start);
    while(!q.empty()){
        start = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            next.x = start.x + move_x[i];
            next.y = start.y + move_y[i];
            if(( next.x <= h && next.x > 0)&&( next.y <= w && next.y > 0) && a[next.x][next.y] == '.')
            {
                a[next.x][next.y] = '#';
                ans++;
                q.push(next);
            }
        }
    }
}
int main(){
    int Wx,Wh,i,j;
    cin>>w>>h;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++){
            cin>>a[i][j];
            if(a[i][j]=='@'){
                Wx = j;
                Wh = i;
            }
        }
    BFS(Wh,Wx);
    printf("%d",ans);
    return 0;
}

可以看到，题解当中运用到了queue容器，由此想到bfs是不是往往与队列有关，事实上就是如此。

洛谷P1443 马的遍历

#include<cstdio>
#include<queue>
#include<string.h>
#include<algorithm>
#include<utility>
using namespace std;
const int dx[] = {1,1,-1,-1,2,2,-2,-2};
const int dy[] = {2,-2,2,-2,1,-1,1,-1};
int ans[403][403];
queue<pair<int,int> > q;
int main(){
	int n,m,x,y;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	memset(ans,-1,sizeof(ans));
	ans[x][y] = 0;
	q.push(make_pair(x,y));
	while(!q.empty()){
		int px = q.front().first;
		int py = q.front().second;
		for(int i = 0; i < 8; i++){
			int xx = px + dx[i];
			int yy = py + dy[i];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && ans[xx][yy] == -1){
				ans[xx][yy] = ans[px][py] + 1;
				q.push(make_pair(xx,yy));
			}
		}
		q.pop();
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			printf("%-5d",ans[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

逻辑部分与红黑瓷砖相似，注意输出时%-5d为左对齐，%5d则是右对齐。
该处运用到了部分stl的内容，pair，一个可以存放两个数字的容器。