首页 > 代码库 > BFS简单题套路_Codevs 1215 迷宫
BFS简单题套路_Codevs 1215 迷宫
BFS 简单题套路
1. 遇到迷宫之类的简单题，有什么行走方向的，先写下面的 声明
const int maxn = 20;struct Status { int r, c; Status(int r = 0, int c = 0) : r(r), c(c) {}// int DIR;};int N; //迷宫数量 int W; //迷宫宽度 char map[maxn][maxn]; //地图 //方向 : 分别代表 上、右、下、左向量 int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };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 = 20;struct Status { int r, c; Status(int r = 0, int c = 0) : r(r), c(c) {}// int DIR;};int N; //迷宫数量 int W; //迷宫宽度 char map[maxn][maxn]; //地图 //方向 : 分别代表 上、右、下、左向量 int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };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, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); while (!que.empty()) que.pop(); scanf("%d", &W); getchar(); for (int i = 0; i < W; i++) { scanf("%s", map[i]); }}bool judge(int r, int c){ return (r >= 0 && r < W) && (c >= 0 && c < W) && map[r][c] != ‘#‘;}bool check(int r, int c){ return (r == W-1 && c == W-1) && 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][0]; tmpy += dir[k][1]; //判断是否越界, 是否是路, 是否走过 if (!judge(tmpx, tmpy) || vis[tmpx][tmpy]) return; if (check(tmpx, tmpy)) { printf("YES\n"); exit(0); } vis[tmpx][tmpy] = true; que.push(Status(tmpx, tmpy));}void BFS(){ que.push(Status(0, 0)); while (!que.empty()) { Status now = que.front(); que.pop(); int r = now.r, c = now.c; for (int k = 0; k < 4; k++) { Move(now, r, c, k); } } printf("NO\n");}void solve(){ scanf("%d", &N); while (N--) { input(); BFS(); }}int main(){ solve(); return 0; }
BFS简单题套路_Codevs 1215 迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。