sdut ——找朋友（广度优先搜索）

2019-11-08 19:25:56

字体：大中小

来源：转载

供稿：网友

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****************************************************/

上一篇：MyEclipse开发XML文件不提示的问题

下一篇：C#的单元测试方法