POJ 3083 Children of the Candy Corn (DFS + BFS)
2024-09-01 08:09:49
题意：
给一个h*w的地图.
'#'表示墙；
'.'表示空地；
'S'表示起点；
'E'表示终点；
1）在地图中仅有一个'S'和一个'E'，他们为位于地图的边墙，不在墙角；
2）地图的四周是墙，还有'S'和'E'；
3)'S'和'E'之间至少有一个'#'将他们分开；
4)'S'和'E'是可以到达的；
按顺序依次打印出从起点开始靠左行走，靠右行走，最短路径的的数量（包括‘S’和‘E’），仅允许水平或垂直方向。
思路：
这道题最麻烦的就是靠左，靠右，其实也只要弄懂靠左，靠右也就出来了，下面只说一下靠左是怎么走的，靠右自己对应着想想。
我们数字依次代表（左上右下）（0 1 2 3）
当前位置 搜索顺序
1 0 1 2 3
2 1 2 3 0
3 2 3 0 1
0 3 0 1 2
仔细想想是不是每次都是靠左边最开始搜，其实靠有就是反向想想，靠左是顺时针，靠右就是逆时针（想想是不是）
最后最短路径就bfs就行了，注意数组大小等等，小心RE，我就在这个错了好多次。
AC代码 + 部分测试数据
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 50;
char Map[maxn][maxn]; //地图
int vis[maxn][maxn];//标记数组
int w, h, sx, sy, zx, zy, ans, flag;
struct node{
int x, y, step;
};
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};//方向数组
bool check(int dx, int dy) {
if(dx >= 0 && dx < h && dy >= 0 && dy < w && Map[dx][dy] != '#') {
return true;
}
else return false;
}
void dfs_left(int x, int y, int k) {
if(x == zx && y == zy) {
flag = 1;//标记返回
return;
}
else {
k = (k+3) % 4;
for(int i = k; i <= k+3; i++) {
int dx = x + dr[(i+4)%4];//这个是在得出搜索顺序后找规律
int dy = y + dc[(i+4)%4];
if(check(dx, dy)) {
ans++;
dfs_left(dx, dy, i%4);
if(flag == 1)
return;
}
}
}
}
void dfs_right(int x, int y, int k) {
if(x == zx && y == zy) {
flag = 1;
return;
}
else {
k = k + 1;
for(int i = k; i >= k-3; i--) {
int dx = x + dr[(i+4)%4];
int dy = y + dc[(i+4)%4];
if(check(dx, dy)) {
ans++;
dfs_right(dx, dy, i%4);
if(flag == 1)
return;
}
}
}
}
int bfs(int x, int y) {
queue<node>q;
vis[x][y] = 1;
node st;
st.x = x;st.y = y;st.step = 1;
q.push(st);
while(!q.empty()) {
node e = q.front();
q.pop();
if(e.x == zx && e.y == zy)return e.step;
for(int i = 0; i < 4 ; i++) {
int dx = e.x + dr[i];
int dy = e.y + dc[i];
if(check(dx, dy) && !vis[dx][dy]) {
vis[dx][dy] = 1;
node now;
now.x = dx;now.y = dy;now.step = e.step + 1;
q.push(now);
}
}
}
}
int main() {
int t;
cin >> t;
while(t--) {
cin >> w >> h;
for(int i = 0; i < h; i++) {
cin >> Map[i];
for(int j = 0; j < w; j++) {
if(Map[i][j] == 'S') {//得到起点坐标
sx = i;
sy = j;
}
if(Map[i][j] == 'E') {//得到终点坐标
zx = i;
zy = j;
}
}
}
ans = 1;flag = 0;//初始化
dfs_left(sx, sy, 0);//向左搜索
cout << ans << " ";
ans = 1;flag = 0;//初始化
dfs_right(sx, sy, 0);//向右搜索
cout << ans << " ";
memset(vis, 0, sizeof(vis));//最bfs时的vis标记数组初始化
cout << bfs(sx, sy) << endl;//bfs最短路径输出结果
}
return 0;
} 部分测试数据：
//Input:
7
8 8
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E####
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########
3 3
###
S.#
#E#
40 40
######################################E#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#......................................#
#S######################################
40 40
########################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#......................................#
#S#E####################################
40 40
#E######################################
S......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
######################################.#
#......................................#
#......................................#
########################################
11 11
#S#########
#.........#
#.#.#.#.#.#
#...#...#.#
#####.###.#
#...#.#...#
#.#...#.#.#
#..##.#...#
#.#.#.###.#
#...#.#...#
#####E#####
/*=======================================================*/
Output:
37 5 5
17 17 9
3 3 3
77 77 77
1481 5 5
3 1483 3
47 45 15最新文章
- React Native文件介绍
- 转WCF Proxy Authentication Required
- MySQL-->基础-->002-->MySQL存储引擎
- 【转】【编码】ASCII 、UNICODE和UTF-8之二
- 利用dedecms autoindex让文章列表加上序列号
- Java发展史之Java由来
- wuzhicms访问统计实现方法
- 1个小时学会ReactiveCocoa基本使用
- WPF学习之数据绑定
- asp.net 开发 sql server 转 oracle
- HTML的TextArea中保存格式的问题
- Python高阶函数之 - 装饰器
- Spring MVC 响应视图（六）
- Fiddler抓包【5】_Fiddler过滤
- 轮播插件swiper
- C#中 property 与 attribute的区别
- shell脚本实例-mysql多机部署
- MSSQL在线文件还原脚本
- MySQL忘记密码了怎么办？
- Mybatis通过注解方式实现批量插入数据库