HDU1312 Red and Black(简单BFS)

HDU1312 Red and Black(简单BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1312

题意:给你一个R*C的网格,网格只有黑格和红格,初始你在一个黑格上,然后你只能走黑格,问你最多能走多少个黑格.(包括起点)

分析:直接BFS,算是最基础的BFS了吧.

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=25;
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
int R,C;
char map[maxn][maxn];
int vis[maxn][maxn];
int BFS(int sr,int sc)
{
    queue<int> Q;
    memset(vis,0,sizeof(vis));
    Q.push(sr*C+sc);
    vis[sr][sc]=1;
    int sum=1;//走过的总黑格数
    while(!Q.empty())
    {
        int pos=Q.front(); Q.pop();
        int r=pos/C, c=pos%C;
        for(int d=0;d<4;d++)
        {
            int nr=r+dr[d], nc=c+dc[d];
            if(nr<0||nr>=R||nc<0||nc>=C||vis[nr][nc]||map[nr][nc]=='#') continue;
            vis[nr][nc]=1;
            Q.push(nr*C+nc);
            sum++;
        }
    }
    return sum;
}
int main()
{
    while(scanf("%d%d",&C,&R)==2)//输入这里要注意R和C要互换位置
    {
        if(C==0&&R==0) break;
        int sr,sc;
        for(int i=0;i<R;i++)
        {
            scanf("%s",map[i]);
            for(int j=0;map[i][j];j++)if(map[i][j]=='@')
                sr=i,sc=j;
        }
        printf("%d\n",BFS(sr,sc));
    }
    return 0;
}