think: 1今天上午做了一上午才AC這個題目，感覺后臺數據有非法輸入，一開始自己用的int型map數組通過輸入的字符的四種情況來判斷map的值，可是樣本數據正確提交卻一直wrong answer,呃，感人的測試結果，剛才自己把猜測的非法數據解決方案輸入了，還是wrong answer，看來應該是沒有非法數據，這樣的話錯誤應該還是在對應關系上不對，欲哭無淚狀，剛才把字符串對應的換了對應關系，然后就AC了，也就說對應關系也對，感覺還是因為int型map數組記錄對應關系可能沒有對應上，因為用char型map數組，自己試過的兩組對應關系都正確 2感覺自己一上午在找錯誤，導致廣度優先搜索的知識可能學的比較少，回顧一下這個題目自己學到的，一隊列是一種思想，就像這個題目，用的不再是一個一維數組作為隊列思想的載體，而是一個結構體數組作為隊列思想的載體，這也就印證的隊列是一種思想，而不是單一的模板，通過這種思想，可以延伸出很多的模板，字符型，結構數組等等，二圖的visit數組不一定是一維數組，就像這個題目就是一個二維數組，應根據題目的具體情況來選用，本題的圖就像是一種坐標系，在坐標系內完成自己題目任務，這也就意味著前面的圖類似于一種連點成線，多點成面的圖結構
sdut原題鏈接
找朋友 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description X，作為戶外運動的忠實愛好者，總是不想呆在家里。現在，他想把死宅Y從家里拉出來。問從X的家到Y的家的最短時間是多少。 為了簡化問題，我們把地圖抽象為n*m的矩陣，行編號從上到下為1 到 n，列編號從左到右為1 到 m。矩陣中’X’表示X所在的初始坐標，’Y’表示Y的位置 , ’#’表示當前位置不能走，’ * ’表示當前位置可以通行。X每次只能向上下左右的相鄰的 ’*’ 移動，每移動一次耗時1秒。
Input 多組輸入。每組測試數據首先輸入兩個整數n，m(1<= n ,m<=15 )表示地圖大小。接下來的n 行，每行m個字符。保證輸入數據合法。
Output 若X可以到達Y的家，輸出最少時間，否則輸出 -1。
Example Input——(輸入無’/’符號) /3 3 /X#Y /* /#*# /3 3 /X#Y /# /#*#
Example Output
4 -1
Hint
Author zmx
以下為accepted代碼——char型map數組
#include <stdio.h>#include <string.h>struct node{ int x; int y; int z;} link[404], ans;char mp[20][20];int visit[20][20];int tp, op, tn, tm, x1, x2, y1, y2;int jn[] = { 0, 0, -1, 1};int jm[] = { 1, -1, 0, 0};int BFS(int n, int m){ link[tp].x = x1, link[tp].y = y1, link[tp].z = 0; visit[link[tp].x][link[tp].y] = 1; tp++; while(op < tp) { ans = link[op++]; if(mp[ans.x][ans.y] == 'Y') { return ans.z; } for(int i = 0; i < 4; i++) { tn = ans.x + jn[i]; tm = ans.y + jm[i]; if(tn >= 0 && tn < n && tm >= 0 && tm < m) { if(mp[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 n, m, i, j; while(scanf("%d %d", &n, &m) != EOF) { //getchar(); tp = op = 0; memset(visit, 0, sizeof(visit)); for(i = 0; i < n; i++) { scanf("%s", mp[i]); } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(mp[i][j] == 'X') { x1 = i, y1 = j; break; } } if(j != m) break; } printf("%d/n", BFS(n, m)); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 112KBSubmit time: 2017-02-16 11:35:27****************************************************/以下為accepted代碼——char型map數組
#include <stdio.h>#include <string.h>struct node{ int x; int y; int z;} link[404], ans;char mp[20][20];int visit[20][20];int tp, op, tn, tm, x1, x2, y1, y2;int jn[] = { 0, 0, -1, 1};int jm[] = { 1, -1, 0, 0};int BFS(int n, int m){ link[tp].x = x1; link[tp].y = y1; link[tp].z = 0; visit[link[tp].x][link[tp].y] = 1; tp++; while(op < tp) { ans = link[op++]; if(mp[ans.x][ans.y-1] == 'Y') { return ans.z; } for(int i = 0; i < 4; i++) { tn = ans.x + jn[i]; tm = ans.y + jm[i]; if(tn >= 1 && tn <= n && tm >= 1 && tm <= m) { if(mp[tn][tm-1] != '#' && 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 n, m, i, j; while(scanf("%d %d", &n, &m) != EOF) { //getchar(); tp = op = 0; memset(visit, 0, sizeof(visit)); for(i = 1; i <= n; i++) scanf("%*c%s", mp[i]); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { if(mp[i][j-1] == 'X') { x1 = i, y1 = j; break; } } if(j != m+1) break; } printf("%d/n", BFS(n, m)); } return 0;}/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 120KBSubmit time: 2017-02-16 11:59:25****************************************************/以下為wrong answer代碼——int型map數組
#include <stdio.h>#include <string.h>struct node{ int x; int y; int z;} link[404], ans;int a[20][20], visit[20][20];int tp, op, tn, tm, x1, x2, y1, y2;int jn[] = { 0, 0, -1, 1};int jm[] = { 1, -1, 0, 0};int BFS(int n, int m){ link[tp].x = x1, link[tp].y = y1, link[tp].z = 0; visit[link[tp].x][link[tp].y] = 1; tp++; while(op < tp) { ans = link[op++]; if(ans.x == x2 && ans.y == y2) { return ans.z; } for(int i = 0; i < 4; i++) { tn = ans.x + jn[i]; tm = ans.y + jm[i]; if(tn >= 1 && tn <= n && tm >= 1 && tm <= m) { if(a[tn][tm] == 1 && 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 n, m, i, j; char s[20], c; while(scanf("%d %d", &n, &m) != EOF) { //getchar(); tp = op = 0; memset(a, 0, sizeof(a)); memset(visit, 0, sizeof(visit)); for(i = 1; i <= n; i++) { scanf("%s", s); for(j = 1; j <= m; j++) { c = s[j-1]; if(c == 'X') { x1 = i, y1 = j, a[i][j] = 1; } else if(c == 'Y') { x2 = i, y2 = j, a[i][j] = 1; } else if(c == '#') { a[i][j] = 0; } else if(c == '*') { a[i][j] = 1; } } } if(n == 1 && m == 1) printf("0/n"); else printf("%d/n", BFS(n, m)); } return 0;}/***************************************************User name: Result: Wrong AnswerTake time: 0msTake Memory: 116KBSubmit time: 2017-02-16 12:07:44****************************************************/新聞熱點
疑難解答
