nyoj 284 坦克大战 简单搜索

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=284

题意：在一个给定图中，铁墙，河流不可走，砖墙走的话，多花费时间1，问从起点到终点至少需要多少时间。

思路：简单广搜~

代码如下：

#include "stdio.h"   //nyoj 284 坦克大战 简单搜索
#include "string.h"
#include "queue"
using namespace std;

#define N 305
#define INF 0x3fffffff

int n,m;
char map[N][N];
int Time[N][N];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

struct node
{
    int x,y;
    int time;
}start,end;

bool Budge(node a)
{
    if(a.x<0 || a.x>=n || a.y<0 || a.y>=m || map[a.x][a.y]=='S' || map[a.x][a.y]=='R')
        return true;
    return false;
}

int BFS()
{
    int i;
    queue<node> q;
    q.push(start);
    node cur,next;
    while(!q.empty())
    {
        cur = q.front();
        q.pop();
        for(i=0; i<4; ++i)
        {
            next.x = cur.x+dir[i][0];
            next.y = cur.y+dir[i][1];
            if(Budge(next)) continue;  //该点越界或不可走，continue;
            next.time = cur.time+1;
            if(map[next.x][next.y]=='B')
                next.time++;
            if(next.time<Time[next.x][next.y]) //该点访问的时间比原时间短，更新时间并将点加入队列
            {
                Time[next.x][next.y] = next.time;
                q.push(next);
            }
        }
    }
    if(Time[end.x][end.y]==INF) return -1;
    return Time[end.x][end.y];
}

int main()
{
    int i,j;
    while(scanf("%d %d",&n,&m),n||m)
    {
        getchar();
        for(i=0;i<n; ++i)
            scanf("%s",map[i]);
        for(i=0; i<n; ++i)
        {
            for(j=0; j<m;++j)
            {
                Time[i][j] = INF;
                if(map[i][j]=='Y')
                    start.x=i,start.y=j,start.time=0;
                if(map[i][j]=='T')
                    end.x=i,end.y=j;
            }
        }
        printf("%d
",BFS());
    }
    return 0;

}