link:http://acm.csu.edu.cn/OnlineJudge/problem.php?cid=2024&pid=7

哈哈,多亏了肖老板了,记得上次肖老板说求什么最小步数什么的一般都用bfs。。所以看到这题时很快就知道怎么下手了~~就是做的时候的有dian小纠结、、、理清思路还是蛮好理解的、。。上我拙劣的代码。。吼吼

code:

#include<iostream>

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
 
char map[101][101];
int vis[101][101];
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n;
 
struct point
{
    int x;
    int y;
    int num;
}s,p,t;
queue<point> q;
 
void bfs()
{
    int i,j,k,x,y;
    while(!q.empty())
    q.pop();
    q.push(s);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(k = 0; k < 4; k++)
        {
            x=p.x+move[k][0];
            y=p.y+move[k][1];
            if(x>=0&&y>=0&&x<n&&y<n&&!vis[x][y]&& map[x][y]!='1')
            {
                t.x=x;
                t.y=y;
                vis[x][y]=1;
                t.num=p.num+1;
                if(map[x][y]=='0')
                    q.push(t);
                else if(map[x][y]=='E')
        {
            printf("%d\n",t.num);
            return;
        }
                else
                {
                    q.push(t);
                    for(i = 0; i < n; i++)
                    {
                        for(j = 0; j < n; j++)
                        {
                            if(!vis[i][j] && map[i][j] == map[x][y])
                            {
                                s.x = i;
                s.y = j;
                s.num = t.num;
                                q.push(s);
                            }
            }
            }
                }
            }
        }
    }
    printf("Oh No!\n");
}
 
int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++)
        {
        getchar();
            for(j=0;j<n;j++)
            {
        scanf("%c",&map[i][j]);
                if(map[i][j]=='S')
                {
                    s.x = i;
                    s.y = j;
                    s.num = 0;
                    vis[i][j] = 1;
                }
            }
        }
    bfs();
    }
    return 0;
}
菜鸟之作,仅供can考,如有错误,请您指出——Tamara

发表评论

电子邮件地址不会被公开。

Post Navigation