题目描述

有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。

思路

暴力搜索就可以了
O(nm)

#include <stdio.h>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int a[101][101],x,y;
int f[101][101],ans=0;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int n,m;
int bfs()
{
    queue<int> tx;
    queue<int> ty;
    tx.push(x); ty.push(y);
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front();
        tx.pop(); ty.pop();
        for (int i=1;i<=4;i++)
            if (dx[i]+xx>=1&&dx[i]+xx<=n&&dy[i]+yy>=1&&dy[i]+yy<=m&&a[dx[i]+xx][dy[i]+yy]==0&&f[dx[i]+xx][dy[i]+yy]==0)
            {
                f[dx[i]+xx][dy[i]+yy]=1;
                ans++;
                tx.push(dx[i]+xx);
                ty.push(dy[i]+yy);
            }
    }           
}
int main()
{
    scanf("%d%d",&m,&n);
    while (n!=0)
    {
        for (int i=1;i<=100;i++)
            for (int j=1;j<=100;j++)
            {
                a[i][j]=f[i][j]=0;
            }
        for (int i=1;i<=n;i++)
        {
            char ch[100];
            scanf("%s",&ch);
            for (int j=1;j<=m;j++)
            {
                if (ch[j-1]=='#')
                    a[i][j]=1;
                if (ch[j-1]=='@')
                {
                    x=i; y=j; f[i][j]=1;
                }
            }
        }
        ans=1;
        bfs();
        printf("%d\n",ans);
        scanf("%d%d",&m,&n);
    }
}