【OJ】1086: 地砖问题

这个问题在理解了BFS算法之后就能很快的写出了，个人感觉BFS和DFS就是状态之间的转换，就是从一个状态转移到另外一个状态，所以我首先定义好了状态，具体的事宜且见下面的代码:

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;// 定义状态
struct Status {int x;int y;
};// 保存地图
char map[25][25];// 标志地图中的每个点是否被访问过 如果访问过则为true
bool mark[25][25];// 四个方向 ----> 上下左右
int go[][2] = {1,0,-1,0,0,1,0,-1
};queue<Status>Q;bool check(int x, int y,int H,int W) {// 检查位置(x,y) 是否可以访问if (x<1 || x>H || y<1 || y>W || mark[x][y] == true || map[x][y] == '#') {return false;}return true;
}// 使用引用来保存答案
void BFS(int &ret, int H, int W)
{while (!Q.empty()) {Status cur = Q.front();Q.pop();ret++;for (int i = 0; i < 4; i++) {// 得到当前位置的下一个位置  有四种可能 即上下左右 int nx = cur.x + go[i][0];// 下一个位置的x坐标int ny = cur.y + go[i][1];// 下一个位置的y坐标Status t;// 生成新的状态t.x = nx;t.y = ny;if (check(nx, ny, H, W)) {// 如果新的状态符合要求   就入队  Q.push(t);mark[nx][ny] = true;  // 标记为已经访问过}}}
}int main()
{int W, H;while (scanf("%d%d", &W, &H) != EOF) {getchar();//干掉输入W、H后的那个回车if (W == 0 && H == 0)break;// 清空上一次的输入for (int i = 0; i < 25; i++) {for (int j = 0; j < 25; j++) {mark[i][j] = false;map[i][j] = 0;}}while (!Q.empty()) {Q.pop();}// 进入本次输入for (int i = 1; i <= H; i++) {// 按照每一行直接输进去scanf("%s", map[i] + 1);// 注意这里的%s    map[i]+1}// 初始化Status head;for (int i = 1; i <= H; i++) {for (int j = 1; j <= W; j++) {if (map[i][j] == '@') {head.x = i;head.y = j;mark[i][j] = true;}}}Q.push(head);// ret用来保存答案int ret = 0;// 调用BFS函数BFS(ret, H, W);printf("%d\n", ret);}return 0;
}

路漫漫其修远兮，吾将上下而求索！