Poj(2312),坦克大战，BFS的变形

挺有趣的一道题目，然而很容易WA，我就WA了一次，虽然我Debug的时候已经知道哪里出问题了，就是比如说我搜到B和E时，从B搜第三个点，B左边的E就被搜了，step为3，然而其实他是step为2，

这里的处理方法很是巧妙，可以从B出发时，把B换成E，step+1,形成一个新的结点加入到队列中去.

之后，和杰哥交流了这下题，我对这个BFS又有了新的一点认识，BFS时，每次搜索的点，都要是同一级别的点，想这里B，和E就不是同一级别的点，所以将这个B,分成两部，注意B搜完后不要标记，B还没有访问完。

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

int to[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};

struct Point
{
    int r,c;
    int step;
};
int r,c;
char maps[305][305];
bool vis[305][305];

bool judge (int rx,int cx)
{
    if(rx<0||rx>=r||cx<0||cx>=c||maps[rx][cx]=='S'||maps[rx][cx]=='R'||vis[rx][cx])
        return true;
    else return false;
}

int main()
{
    int sr,sc;
    while(scanf("%d%d",&r,&c),r)
    {
        memset(vis,false,sizeof(vis));

        for(int i=0; i<r; i++)
        {
            scanf("%s",maps[i]);
            for(int j=0; j<c; j++)
            {
                if(maps[i][j]=='Y')
                {
                    sr = i;
                    sc = j;
                }
            }
        }
        int ans = -1;

        queue<Point> Q;
        Point a,next;
        a.r = sr;
        a.c = sc;
        a.step = 0;
        vis[a.r][a.c] = true;
        Q.push(a);
        while(!Q.empty())
        {
            a = Q.front();
            Q.pop();

            if(maps[a.r][a.c]=='T')
            {
                ans = a.step;
                break;
            }
            if(maps[a.r][a.c]=='B')
            {
                a.step ++;
                maps[a.r][a.c] = 'E';
                Q.push(a);
                continue;
            }

            for(int i=0; i<4; i++)
            {
                next.r = a.r + to[i][0];
                next.c = a.c + to[i][1];
                if(judge(next.r,next.c))
                    continue;
                vis[next.r][next.c] = true;
                next.step = a.step +1;
                Q.push(next);

            }

        }
        printf("%d
",ans);
    }
    return 0;
}

Poj(2312),坦克大战，BFS的变形

相关推荐