think: 1廣度優(yōu)先搜索+char型map數(shù)組
sdut原題鏈接
湯圓の拯救計劃 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 又到了湯圓星球一年一度的湯圓節(jié)了，但是大魔王卻過來把湯圓公主抓走了Σ( ° △ °|||)︴ 身為湯圓騎士的QAQ蒟蒻自然而然的肩負(fù)著拯救湯圓的使命 QAQ蒟蒻經(jīng)歷了千辛萬苦（并沒有）之后，來到了大魔王的城堡，根據(jù)情報，湯圓公主就被大魔王放在城堡內(nèi)，然后QAQ蒟蒻發(fā)現(xiàn)自己是一個路 癡，所幸的是他拿到了大魔王的城堡的地圖，而且在這上面標(biāo)注了自己和湯圓公主的位置，那么問題來了，聰明的你能幫他計算出需要多少單位 的時間來趕到湯圓公主的位置嗎？ Ps：QAQ蒟蒻每一次都可以移動到相鄰的非墻的格子中，每次移動都要花費1個單位的時間 有公共邊的格子定義為相鄰
Input 一開始為一個整數(shù)T代表一共有T組數(shù)據(jù) 每組測試數(shù)據(jù)的第一行有兩個整數(shù)n,m (2<=n,m<=300) 接下來的n行m列為大魔王的迷宮，其中 ’#’為墻壁，‘_‘為地面 A代表QAQ蒟蒻，O代表湯圓公主:
Output 一組數(shù)據(jù)輸出一個整數(shù)代表從QAQ蒟蒻到湯圓的位置的最短時間 如果QAQ蒟蒻不能到達(dá)湯圓的位置，輸出-1
Example Input 2 3 3 __A _## __O 2 2 A# /#O(實際輸入無’/’符號)
Example Output 6 -1
Hint
Author QAsQ
以下為accepted代碼
#include <stdio.h>#include <string.h>struct node{ int x; int y; int z;}link[90000], ans;char map[300][300];int tp, op, x1, y1, visit[300][300];int fn[] = {0, 0, -1, 1};int fm[] = {1, -1, 0, 0};int BFS(int n, int m){ int tn, tm; link[tp].x = x1; link[tp].y = y1; link[tp].z = 0; tp++; visit[x1][y1] = 1; while(op < tp) { ans = link[op++]; if(map[ans.x][ans.y] == 'O') { return ans.z; } for(int i = 0; i < 4; i++) { tn = ans.x + fn[i]; tm = ans.y + fm[i]; if(tn >= 0 && tn < n && tm >= 0 && tm < m) { if(map[tn][tm] != '#' && visit[tn][tm] == 0) { link[tp].x = tn; link[tp].y = tm; link[tp].z = ans.z + 1; tp++; visit[tn][tm] = 1; } } } } return -1;}int main(){ int T, n, m, i, j; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); tp = op = 0; memset(visit, 0, sizeof(visit)); for(i = 0; i < n; i++) { scanf("%s", map[i]); } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(map[i][j] == 'A') { x1 = i, y1 = j; break; } } if(j != m) break; } printf("%d/n", BFS(n, m)); } return 0;}/***************************************************User name: Result: AcceptedTake time: 4msTake Memory: 760KBSubmit time: 2017-02-16 14:56:21****************************************************/代碼是程序員的朋友，雖然沒有熱情，但是非常忠實。
新聞熱點
疑難解答
