BFS简单题套路_Codevs 1215 迷宫

BFS 简单题套路

1. 遇到迷宫之类的简单题,有什么行走方向的,先写下面的 声明

const int maxn = ;
struct Status {
int r, c;
Status(int r = , int c = ) : r(r), c(c) {}
// int DIR;
};
int N; //迷宫数量
int W; //迷宫宽度
char map[maxn][maxn]; //地图
//方向 : 分别代表 上、右、下、左向量
int dir[][] = { {-, }, {, }, {, }, {, -} };
bool vis[maxn][maxn];
//队列
queue<Status> que; void input(); //输入数据
bool judge(int r, int c);//判断是否越界, 是否是路
bool check(int r, int c);//判断当前是否到达终点
//移动一步
void Move(const Status& now, int r, int c, int k);
void BFS(); //BFS搜索
void solve();

2. 随后再逐个函数的实现

//完整代码
/*
* Codevs 1215 迷宫
*/
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std; const int maxn = ;
struct Status {
int r, c;
Status(int r = , int c = ) : r(r), c(c) {}
// int DIR;
};
int N; //迷宫数量
int W; //迷宫宽度
char map[maxn][maxn]; //地图
//方向 : 分别代表 上、右、下、左向量
int dir[][] = { {-, }, {, }, {, }, {, -} };
bool vis[maxn][maxn];
//队列
queue<Status> que; void input(); //输入数据
bool judge(int r, int c);//判断是否越界, 是否是路
bool check(int r, int c);//判断当前是否到达终点
//移动一步
void Move(const Status& now, int r, int c, int k);
void BFS(); //BFS搜索
void solve(); //启动 void input()
{
memset(map, , sizeof(map));
memset(vis, , sizeof(vis));
while (!que.empty()) que.pop();
scanf("%d", &W);
getchar();
for (int i = ; i < W; i++) {
scanf("%s", map[i]);
}
} bool judge(int r, int c)
{
return (r >= && r < W) && (c >= && c < W)
&& map[r][c] != '#';
} bool check(int r, int c)
{
return (r == W- && c == W-) && map[r][c] == 'e';
} void Move(const Status& now, int r, int c, int k)
{
Status tmp = now;
int tmpx = tmp.r;
int tmpy = tmp.c; tmpx += dir[k][];
tmpy += dir[k][]; //判断是否越界, 是否是路, 是否走过
if (!judge(tmpx, tmpy) || vis[tmpx][tmpy]) return; if (check(tmpx, tmpy)) {
printf("YES\n");
exit();
}
vis[tmpx][tmpy] = true;
que.push(Status(tmpx, tmpy));
} void BFS()
{
que.push(Status(, ));
while (!que.empty())
{
Status now = que.front(); que.pop();
int r = now.r, c = now.c;
for (int k = ; k < ; k++) {
Move(now, r, c, k);
}
}
printf("NO\n");
} void solve()
{
scanf("%d", &N);
while (N--) {
input();
BFS();
}
} int main()
{
solve();
return ;
}
上一篇:安装yum源和gcc编译器遇到的问题


下一篇:Qt学习记录--02 Qt的信号槽机制介绍(含Qt5与Qt4的差异对比)