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

深藏阁楼爱情的钟 2022-07-12 07:25 93阅读 0赞

think:  
1今天上午做了一上午才AC这个题目，感觉后台数据有非法输入，一开始自己用的int型map数组通过输入的字符的四种情况来判断map的值，可是样本数据正确提交却一直wrong answer,呃，感人的测试结果，刚才自己把猜测的非法数据解决方案输入了，还是wrong answer，看来应该是没有非法数据，这样的话错误应该还是在对应关系上不对，欲哭无泪状，刚才把字符串对应的换了对应关系，然后就AC了，也就说对应关系也对，感觉还是因为int型map数组记录对应关系可能没有对应上，因为用char型map数组，自己试过的两组对应关系都正确  
2感觉自己一上午在找错误，导致广度优先搜索的知识可能学的比较少，回顾一下这个题目自己学到的，一队列是一种思想，就像这个题目，用的不再是一个一维数组作为队列思想的载体，而是一个结构体数组作为队列思想的载体，这也就印证的队列是一种思想，而不是单一的模板，通过这种思想，可以延伸出很多的模板，字符型，结构数组等等，二图的visit数组不一定是一维数组，就像这个题目就是一个二维数组，应根据题目的具体情况来选用，本题的图就像是一种坐标系，在坐标系内完成自己题目任务，这也就意味着前面的图类似于一种连点成线，多点成面的图结构

[sdut原题链接][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: Accepted
    Take time: 0ms
    Take Memory: 112KB
    Submit 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: Accepted
    Take time: 0ms
    Take Memory: 120KB
    Submit 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 Answer
    Take time: 0ms
    Take Memory: 116KB
    Submit time: 2017-02-16 12:07:44
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2012/pid/2779