C. Robot

There is a rectangular field in the lab of Institution of Advanced Robotic Technology.

Many robots are about to release to this field one after another. They always enter the field from the upper left cell and leave from the lower right cell. In between, they can move vertically or horizontally to an adjacent cell on each step. At any time, there is at most one robot on the field.

Robots can be divided into two types: Type A and Type B. During the movement, a robot will write down its type mark (A or B) in each cell on its track, which will cover all previous marks in the same cell. Notice that there is no mark on the field at the beginning.

Here is an example: initially there is no mark on the field (Figure 1); first, a robot of type A crosses the field from top-left to bottom right (Figure 2). After that, a robot of type B crosses and its tracks are partially covering the A’s (Figure 3).

                    .....          AAAA.          BBAA.
                    .....          ..AA.          .BBBB
                    .....          ...A.          ...AB
                    .....          .AAA.          .ABBB
                    .....          ..AAA          ..BBB
                     (1)            (2)            (3)

You are given the marks on the field after all robots have crossed. Write a program to determine the minimal possible number of released robots.

2
3 3
AA.
.A.
.AA
5 8
AAB.....
.ABBB...
.AAAAA..
..BBBAAB
.....AAA

1
2

#include<stdio.h>
#include<queue>
#include<iostream>
using namespace std;
typedef struct nnn
{
    int x,y;
}node;
int vist[4005][4005];
char map[4005][4005];
int n,m,k,dir[4][2]={0,1,0,-1,1,0,-1,0},tf;

void init()
{
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    vist[i][j]=0;
}
queue<node>q[2];
void bfs(int flag)
{
    node p,s;
    k++;
    while(!q[flag].empty())
    {
        s=q[flag].front(); q[flag].pop();
        if(s.x==0&&s.y==0)tf=1;
        for(int e=0;e<4;e++)
        {
            p.x=s.x+dir[e][0]; p.y=s.y+dir[e][1];
            if(p.x>=0&&p.x<n&&p.y>=0&&p.y<m&&vist[p.x][p.y]==0&&map[p.x][p.y]!='.')
            {
                vist[p.x][p.y]=1;
                if(map[p.x][p.y]!=map[s.x][s.y])
                    q[!flag].push(p);
                else q[flag].push(p);
            }
        }
    }
}
int main()
{
    int t,f,flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%s",map[i]);
        k=0; tf=0;
        while(!q[0].empty())q[0].pop();
        while(!q[1].empty())q[1].pop();

        if(map[0][0]!=map[n-1][m-1])f=1;else f=0;
        if(map[n-1][m-1]!='.')
        {
            node s;
            init();
            s.x=n-1; s.y=m-1; flag=0;
            vist[n-1][m-1]=1; q[0].push(s);
           while(!q[flag].empty())
           {
               bfs(flag); flag=(!flag);
           }
        }
        else f=0;
        if(tf==0&&f)f=0;
        printf("%d\n",k-f);
    }
}