http://acm.hdu.edu.cn/showproblem.php?pid=1429
1 #include <stdio.h> 2 #include <queue> 3 #include <string.h> 4 using namespace std; 5 struct node 6 { 7 int x,y; 8 int state; 9 int step; 10 } s,t; 11 int Time,n,m; 12 int s_x,s_y,e_x,e_y; 13 char a[32][32]; 14 int vis[32][32][1026];//标记状态 15 int dir[4][2] = {{0,1},{-1,0},{0,-1},{1,0}}; 16 void bfs() 17 { 18 memset(vis,0,sizeof(vis)); 19 queue<node>q; 20 s.x = s_x; 21 s.y = s_y; 22 s.state = 0; 23 s.step = 0; 24 q.push(s); 25 vis[s_x][s_y][s.state] = 1; 26 while(!q.empty()) 27 { 28 t = q.front(); 29 q.pop(); 30 int x = t.x; 31 int y = t.y; 32 if (x==e_x&&y==e_y) 33 { 34 Time = t.step; 35 return ; 36 } 37 for (int i = 0; i < 4; i++) 38 { 39 int dx = x+dir[i][0]; 40 int dy = y+dir[i][1]; 41 42 if (dx>=0&&dx<n && dy>=0&&dy<m && (!vis[dx][dy][t.state]) && a[dx][dy]!='*') 43 { 44 if (a[dx][dy]=='.'||a[dx][dy]=='^'||a[dx][dy]=='@') 45 { 46 vis[dx][dy][t.state] = 1; 47 s.x = dx; 48 s.y = dy; 49 s.step=t.step+1; 50 s.state = t.state; 51 q.push(s); 52 53 } 54 else if (a[dx][dy]>='A' && a[dx][dy]<='J') 55 { 56 if ((1<<(a[dx][dy]-'A'))&t.state)//判断是否拿到过能打开当前门的钥匙 57 { 58 vis[dx][dy][t.state] = 1; 59 s.x = dx; 60 s.y = dy; 61 s.step = t.step+1; 62 s.state = t.state; 63 q.push(s); 64 } 65 } 66 else if (a[dx][dy]>='a' && a[dx][dy] <= 'j') 67 { 68 int state= ((1<<(a[dx][dy]-'a'))|t.state);//更新此时拿到的钥匙的状态 69 if (!vis[dx][dy][state]) 70 { 71 vis[dx][dy][state] = 1; 72 s.x = dx; 73 s.y = dy; 74 s.step = t.step+1; 75 s.state = state; 76 q.push(s); 77 } 78 79 } 80 } 81 } 82 } 83 } 84 int main() 85 { 86 int t; 87 while(~scanf("%d%d%d%*c",&n,&m,&t)) 88 { 89 Time = -1; 90 for (int i = 0; i < n; i++) 91 scanf("%s",a[i]); 92 for (int i = 0; i < n; i++) 93 { 94 for (int j = 0; j < m; j++) 95 { 96 if (a[i][j]=='@') 97 { 98 s_x = i; 99 s_y = j; 100 } 101 if (a[i][j]=='^') 102 { 103 e_x = i; 104 e_y = j; 105 } 106 } 107 } 108 bfs(); 109 if (Time < t && Time!=-1) 110 printf("%d ",Time); 111 else 112 printf("-1 "); 113 } 114 return 0; 115 }