逃离迷宫
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?
Input
第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数,接下来为t组测试数据,每组测试数据中,
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'*'表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2
≤ m),其中k表示gloria最多能转的弯数,(x1, y1), (x2, y2)表示两个位置,其中x1,x2对应列,y1, y2对应行。
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'*'表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2
≤ m),其中k表示gloria最多能转的弯数,(x1, y1), (x2, y2)表示两个位置,其中x1,x2对应列,y1, y2对应行。
Output
每组测试数据对应为一行,若gloria能从一个位置走到另外一个位置,输出“yes”,否则输出“no”。
Sample Input
2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3
Sample Output
no yes
BFS,写了2个小时,每次写BFS都花挺多时间的,各种细节
#include<cstdio> #include<cstring> #include<queue> using namespace std; int n,m; int k,ok; char map[110][110]; int vis[4][110][110]; int ff[4][2]={1,0, 0,1, -1,0, 0,-1}; struct Node{ int x,y; }star,last; struct FF{ int x,y; int flag,cnt; }; bool operator <(FF a,FF b) { return a.cnt>b.cnt; } priority_queue<FF> que; void BFS() { int i,j; while(!que.empty()) que.pop(); FF tmp,a; tmp.x=star.x; tmp.y=star.y; tmp.cnt=0; memset(vis,-1,sizeof(vis)); for(i=0;i<4;i++) { tmp.flag=i; que.push(tmp); vis[tmp.flag][tmp.y][tmp.x]=1; } int tmp_x,tmp_y; ok=0; while(!que.empty()) { tmp=que.top(); que.pop(); if(tmp.cnt>k) return ; if(tmp.x==last.x && tmp.y==last.y) { ok=1; return ; } for(i=0;i<4;i++) { tmp_x=tmp.x+ff[i][0]; tmp_y=tmp.y+ff[i][1]; while(tmp_x>=0 && tmp_x<m && tmp_y>=0 && tmp_y<n && map[tmp_y][tmp_x]=='.') { a.x=tmp_x; a.y=tmp_y; a.flag=i; if(i==tmp.flag) { a.cnt=tmp.cnt; if(vis[a.flag][a.y][a.x]==-1|| vis[a.flag][a.y][a.x]>a.cnt) { vis[a.flag][a.y][a.x]=a.cnt; que.push(a); } } else { a.cnt=tmp.cnt+1; if(vis[a.flag][a.y][a.x]==-1 || vis[a.flag][a.y][a.x]>a.cnt) { vis[a.flag][a.y][a.x]=a.cnt; que.push(a); } break; } tmp_x=tmp_x+ff[i][0]; tmp_y=tmp_y+ff[i][1]; } } } } int main() { int T; int i; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) scanf("%s",map[i]); scanf("%d%d%d%d%d",&k,&star.x,&star.y,&last.x,&last.y); star.x--; star.y--; last.x--; last.y--; BFS(); if(ok) printf("yes\n"); else printf("no\n"); } return 0; }
DFS果断容易写,10来分钟就写好了,1A,速度还比上面的BFS快了很多
#include<cstdio> #include<cstring> int n,m,k; int ok; char map[110][110]; int vis[4][110][110]; struct Node{ int x,y; int cnt; }star,last,tmp; int num[4][2]={0,1, 1,0, -1,0, 0,-1}; void DFS(int x,int y,int flag,int cnt) { if(cnt>k) return ; // printf("%d %d %d %d\n",x,y,flag,cnt); if(x==last.x && y==last.y) { ok=1; } if(ok) return ; for(int i=0;i<4;i++) { tmp.x=x+num[i][0]; tmp.y=y+num[i][1]; if(tmp.x>=0 && tmp.x<n && tmp.y>=0 && tmp.y<m && map[tmp.x][tmp.y]=='.') { if(i==flag) tmp.cnt=cnt; else tmp.cnt=cnt+1; if(vis[i][tmp.x][tmp.y]==-1 || vis[i][tmp.x][tmp.y]>tmp.cnt) { vis[i][tmp.x][tmp.y]=tmp.cnt; DFS(tmp.x,tmp.y,i,tmp.cnt); } } } } int main() { int t,i; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0;i<n;i++) scanf("%s",map[i]); scanf("%d%d%d%d%d",&k,&star.y,&star.x,&last.y,&last.x); star.x--; star.y--; last.x--; last.y--; ok=0; memset(vis,-1,sizeof(vis)); for(i=0;i<4;i++) { vis[i][star.x][star.y]=0; DFS(star.x,star.y,i,0); } if(ok) printf("yes\n"); else printf("no\n"); } return 0; }