「BZOJ3299」[USACO2011 Open] Corn Maze玉米迷宫
Description
今年秋天，约翰带着奶牛们去玩玉米迷宫。迷宫可分成NxM个格子，有些格子种了玉 米，种宥玉米的格子无法通行。
迷宫的四条边界上都是种了玉米的格子，其屮只有一个格子 没种，那就是出口。
在这个迷宫里，有一些神奇的传送点6每个传送点由一对点组成，一旦 走入传送点的某个结点，
机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的，如果你定到了另一头，机器也会把你送回来。
奶牛在一个单位的时间内只能向相邻的四个方向移动一格，不过传送机传送是瞬间完成 的。
现在W西在迷宫里迷路了，她只知道目前的位罝在哪里，请你帮助她用最短的时间走出 迷宫吧。
Input
第一行：两个用空格分开的整数：N和M,2
第二行到N+1行：第i+1行有M个连续的字符，描述了迷宫第i行的信息。其中”#”代 表不能通行的玉米地，
“.”代表可以通行的草地，”@”代表贝西的起始位罝，”=”代表迷宫出口，
大写字母“A”到“Z”总是成对出现的，代表一对传送点
Output
第一行：一个整数，表示贝西走出迷宫的最短时间，保证逃离迷宮的路线一定存在
Sample Input
5 6
###=##
#.W.##
#.####
#.@W##
######
###=##
#.W.##
#.####
#.@W##
######
Sample Output
3
HINT
从起点向右走，通过w传送，再从另一端 走出迷宫
题解
裸的bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; const double pi=acos(-1.0); inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int n,m,bx,by,ex,ey; int a[26][4]; char mp[1005][1005]; bool vis[1005][1005]; struct data{int x,y,step;}q[1000005]; void next(int &x,int &y,char ch) { int t=ch-'A'; if(a[t][0]==x&&a[t][1]==y) x=a[t][2],y=a[t][3]; else x=a[t][0],y=a[t][1]; } void bfs() { int head=0,tail=1; q[head].x=bx;q[head].y=by;vis[bx][by]=1; while(head!=tail) { int x=q[head].x,y=q[head].y,step=q[head].step;head++; for(int i=0;i<4;i++) { int nowx=x+xx[i],nowy=y+yy[i]; if(mp[nowx][nowy]=='#'||vis[nowx][nowy]||nowx<1||nowy<1||nowx>n||nowy>m) continue; vis[nowx][nowy]=1; if(mp[nowx][nowy]>='A'&&mp[nowx][nowy]<='Z') next(nowx,nowy,mp[nowx][nowy]); if(nowx==ex&&nowy==ey){printf("%d\n",step+1);return;} q[tail].x=nowx;q[tail].y=nowy;q[tail].step=step+1;tail++; } } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { scanf("%s",mp[i]+1); for(int j=1;j<=m;j++) { char t=mp[i][j]; if(t>='A'&&t<='Z') { if(!a[t-'A'][0]) a[t-'A'][0]=i,a[t-'A'][1]=j; else a[t-'A'][2]=i,a[t-'A'][3]=j; } else if(t=='@')bx=i,by=j; else if(t=='=')ex=i,ey=j; } } bfs(); return 0; } |
Subscribe
计数器 9314686
OI 课件=>
OI 课件=>