Gym 100971J-Robots at Warehouse

题目链接：http://codeforces.com/gym/100971/problem/J

Vitaly works at the warehouse. The warehouse can be represented as a grid of n × m cells, each of which either is free or is occupied by a container. From every free cell it's possible to reach every other free cell by moving only through the cells sharing a side. Besides that, there are two robots in the warehouse. The robots are located in different free cells.

Vitaly wants to swap the robots. Robots can move only through free cells sharing a side, moreover, they can't be in the same cell at the same time or move through each other. Find out if the swap can be done.

Input

The first line contains two positive integers n and m (2 ≤ n·m ≤ 200000) — the sizes of the warehouse.

Each of the next n lines contains m characters. The j-th character of the i-th line is «.» if the corresponding cell is free, «#» if there is a container on it, «1» if it's occupied by the first robot, and «2» if it's occupied by the second robot. The characters «1» and «2» appear exactly once in these lines.

Output

Output «YES» (without quotes) if the robots can be swapped, and «NO» (without quotes) if that can't be done.

Examples

Input

5 3

###

#1#

#.#

#2#

###

Output

NO

Input

3 5

#...#

#1.2#

#####

Output

YES
题意：简单的来说就是给我们一个n*m的地图，其中里面包括'#'表示不能走，还有'.'表示能走，还有有且仅有一个‘1’和一个‘2’分别表示两个机器人，而我们的任务就是判断是否可以让两个机器人交换位置，两个机器人是不能出现在同一个位置的，如果可以的话输出'YES',否则输出’NO‘。还有最最重要的一点就是所有的'.'都是连在一起的，可能很多人都没看到这个，好吧其实我开始也没看到，这也就表明1和2一定是互通的。可能很多人没看到都会去用BFS和DFS去搜索判断路径吧，这样就复杂多了。
解题思路：既然机器人1和机器人2一定是互通的，我们就只要判断他们是否可以互换了，而不是就只有一条单独宽度为1的道路，这样肯定是会相撞的没法交换的。然后怎么样才能交换呢？这里就可以分成两种的情况了，第一种就是有那种T字路口，最简单的T字路口当然就是直接一条单道旁边有一个空的位置了，只要有一个机器人挺在那个空位就可以实现位置交换了，而另一种情况就是有两条不一样的道路或者说就是个环吧，这样两个机器人分别走两条道就可以实现交换了。现在情况已经分析完了，我们要怎么转换成代码呢？我们知道所有'.'都是连通的，我们就将这些可以去的地方打上标记，定义一个数组标记一下，然后再进行枚举判断是否存在T字路口或者环，判断T字路口的话一般情况道路某个'.'周围应该是有两个'.'的，而如果存在第三个'.'则就可以认为是T字路口了。而判断是否有环的话,因为超过两个'.'的已经在T字路口中判断完了，所以只还有周围存在0、1或2个'.'的情况，因为是连通的 不存在周围0个的情况，而又要形成环的话，我们简单想想就知道应该周围只可以是两个'.'的，所以我们就直接判断道路中的'.'周围是否存在只有一个'.'的，有的话就不是环，没有的话就是了。
附上AC代码：

 #include<iostream>

 #include<cstdio>

 #include<string>

 #include<string.h>

 using namespace std;

 int n,m,x1,y1,x2,y2;

 bool flag=false;

 int dir[][]={{,},{,-},{-,},{,}};

 int main()

 {

     cin>>n>>m;

     getchar();

     char map[n+][m+];

     int vis[n+][m+];

     int num[n+][m+];

     memset(num,,sizeof(num));

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=m;j++)

         {

             scanf("%c",&map[i][j]);

             if(map[i][j]=='')

             {

                 x1=i; y1=j;

                 vis[x1][y1]=;

             }

             if(map[i][j]=='')

             {

                 x2=i; y2=j;

                 vis[x2][y2]=;

             }

             if(map[i][j]=='.')  vis[i][j]=;

         }

         getchar();

     }

     //判断是否存在T字路口或者环（圈圈）

     int tot=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

         {

             if(vis[i][j])

             {

                 if(vis[i][j])

                 {

                 for(int k=;k<;k++)

                 {

                     int dx=i+dir[k][];

                     int dy=j+dir[k][];

                     if(vis[dx][dy]) num[i][j]++;

                 }

                 if(num[i][j]>=) flag=true;  //T字路口

                 if(num[i][j]==) tot++;  //圈圈

                 }

             }

         }

     if(tot==) flag=true;   //全部被标记的点周围只有两个点

     if(flag) cout<<"YES"<<endl;

     else cout<<"NO"<<endl;

     return ;

 }

巴特西

Gym 100971J-Robots at Warehouse

最新文章

热门文章