codevs 2919_选择题_bfs

发布于 2019-05-06  5 次阅读


题目描述

某同学考试,在N*M的答题卡上写了A,B,C,D四种答案。
他做完了,又不能交,一看表,离打铃还有N久。
他开始玩一个游戏:选一个格子X,Y,从这个格子出发向4个方向找相同的选项,找到的再如此。
求形成的图形的面积。(一个选项占一个单位面积)


思路

暴力广搜,加上判重就可以了
O(n*m)


#include 
#include 
#include 
using namespace std;
int a[100][100],fl[100][100];
int n,m,x,y,ans=1;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int bfs()
{
    queue tx;
    queue ty;
    tx.push(x); ty.push(y);
    fl[x][y]=1;
    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]==a[xx][yy]&&fl[dx[i]+xx][dy[i]+yy]==0)
            {
                fl[dx[i]+xx][dy[i]+yy]=1;
                ans++;
                tx.push(dx[i]+xx);
                ty.push(dy[i]+yy);
            }
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for (int i=1;i<=n;i++)
    {
        char ch[100];
        for (int j=1;j<=m;j++)
        {
            scanf("%s",&ch);
            a[i][j]=ch[0];
        }
    }
    bfs();
    printf("%d\n",ans);
}
]]>