一個(gè)有幾個(gè)小坑的bfs

題目很長，但并不復(fù)雜，大概總結(jié)起來有這么點(diǎn)。

有t組輸入

每組輸入n, m, p。表示一個(gè)n*m的地圖，每p秒按鍵會(huì)右移一次（這個(gè)等會(huì)兒再講）。

然后是地圖的輸入。其中'@'為起點(diǎn)，'$'為終點(diǎn)，'.'為通路，'*'為不通。

問從起點(diǎn)到終點(diǎn)最少需要多久？

一眼看去，裸的bfs嘛，10*10的地圖，簡(jiǎn)單！

不過還是連錯(cuò)4次……

?

注意！

每一秒有4種操作，注意，不是三種，1. 光標(biāo)左移，2. 光標(biāo)右移，3. 按照光標(biāo)方向行走，4. 不動(dòng)（尤其是這一個(gè)）。

所謂光標(biāo)左移，右移，因?yàn)轭}目中給出了光標(biāo)（在圖上，共4個(gè)方向），每次改變的移動(dòng)方向只能是當(dāng)前光標(biāo)選擇的方向的左右兩個(gè)。而行走只能按照光標(biāo)所指的方向。

另外每過p秒，方向會(huì)變化（初始四個(gè)方向的順序?yàn)樽笥疑舷?#xff0c;p秒后變成右上下左，再過p秒后變?yōu)樯舷伦笥?#xff09;。

?

廢話說完，上代碼——

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 const int N = 20; 9 10 struct node 11 { 12 int x, y, dis, step; 13 }; 14 15 int go[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; 16 17 int t; 18 int n, m, P; 19 char mp[N][N]; 20 bool v[N][N]; 21 bool vv[N][N][5]; 22 23 int change(int a) 24 { 25 switch(a) 26 { 27 case 0: 28 return 3; 29 case 1: 30 return 0; 31 case 2: 32 return 1; 33 case 3: 34 return 2; 35 } 36 } 37 38 void bfs() 39 { 40 node p; 41 bool k = 0; 42 for(int i = 0; i < n; i++) 43 { 44 for(int j = 0; j < m; j++) 45 { 46 if(mp[i][j] == '@') 47 { 48 p.x = i; 49 p.y = j; 50 k = 1; break; 51 } 52 } 53 if(k) break; 54 } 55 p.dis = 0; 56 p.step = 0; 57 vv[p.x][p.y][0] = 1; 58 59 queue<node> que; 60 que.push(p); 61 while(!que.empty()) 62 { 63 node p = que.front(); 64 que.pop(); 65 66 int xx = p.x+go[p.dis][0]; 67 int yy = p.y+go[p.dis][1]; 68 if(xx >= 0 && xx < n && yy >= 0 && yy < m) 69 { 70 if(v[xx][yy] == 0) 71 { 72 if(mp[xx][yy] == '.') 73 { 74 v[xx][yy] = 1; 75 node q; 76 q.x = xx; 77 q.y = yy; 78 q.step = p.step+1; 79 q.dis = p.dis; 80 if(q.step%P == 0) 81 { 82 q.dis = change(q.dis); 83 vv[xx][yy][q.dis] = 1; 84 } 85 que.push(q); 86 } 87 else if(mp[xx][yy] == '$') 88 { 89 printf("%d\n", p.step+1); 90 return; 91 } 92 } 93 } 94 95 if((p.step+1)%P == 0) {p.dis = change(p.dis);} 96 97 node q; 98 q.x = p.x; 99 q.y = p.y; 100 q.step = p.step+1; 101 102 q.dis = p.dis+1; 103 q.dis %= 4; 104 if(vv[q.x][q.y][q.dis] == 0) 105 { 106 que.push(q); 107 vv[q.x][q.y][q.dis] = 1; 108 } 109 110 q.dis = p.dis+3; 111 q.dis %= 4; 112 if(vv[q.x][q.y][q.dis] == 0) 113 { 114 que.push(q); 115 vv[q.x][q.y][q.dis] = 1; 116 } 117 118 q.dis = p.dis; 119 if(vv[q.x][q.y][q.dis] == 0) 120 { 121 que.push(q); 122 vv[q.x][q.y][q.dis] = 1; 123 } 124 } 125 printf("YouBadbad\n"); 126 } 127 128 int main() 129 { 130 //freopen("test.txt", "r", stdin); 131 scanf("%d", &t); 132 while(t--) 133 { 134 memset(mp, 0, sizeof(mp)); 135 memset(v, 0, sizeof(v)); 136 memset(vv, 0, sizeof(vv)); 137 scanf("%d%d%d", &n, &m, &P); 138 for(int i = 0; i < n; i++) 139 { 140 scanf("%s", mp[i]); 141 } 142 bfs(); 143 } 144 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/mypride/p/4491343.html

總結(jié)

以上是生活随笔為你收集整理的ZOJ3865:Superbot(BFS) The 15th Zhejiang University Programming Contest的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。