Gym

题目链接：http://codeforces.com/gym/100187/problem/E

题解：一开始做的时候是将两幅图合并，然后直接bfs看是否能到达终点。但这种做法的错的，因为走出来的路对于两幅图来说不一定都是最短的。正确做法：

第一步：分别用bfs求出两图的最短路。

第二步：如果最短路长度一样。则将两幅图合并，再bfs，如果能走到终点，且最短路长度仍然等于未合并前的长度，则YES；否则NO。

学习之处：求两个或多个事物所共有的东西，其实就是求交集。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<string>
11 #include<set>
12 //#define LOCAL
13 using namespace std;
14 #define pb push_back
15 #define ms(a, b) memset(a,b,sizeof(a));
16 typedef long long LL;
17 const int inf = 0x3f3f3f3f;
18 const int mod = 1000000007;
19 const int maxn = 10;
20 
21 struct node
22 {
23     int x,y,k;
24 };
25 node now, e;
26 
27 int n,m, vis[550][550];
28 char a[550][550], b[550][550], c[550][550];
29 int d[4][2] = {1,0,-1,0,0,1,0,-1};
30 
31 int bfs(int x, int y, char s[][550])
32 {
33     queue<node>q;
34     memset(vis,0,sizeof(vis));
35     now.x = x;
36     now.y = y;
37     now.k = 0;
38     vis[x][y] = 1;
39     q.push(now);
40 
41     while(!q.empty())
42     {
43         now = q.front();
44         q.pop();
45 
46         if(now.x==n && now.y==m)
47                 return now.k;
48 
49         for(int i = 0; i<4; i++)
50         {
51             e.x = now.x + d[i][0];
52             e.y = now.y + d[i][1];
53             e.k = now.k + 1;
54 
55             if(e.x<1 || e.x>n || e.y<1 || e.y>m || vis[e.x][e.y] || s[e.x][e.y]=='#')
56                 continue;
57                 
58             vis[e.x][e.y] = 1;
59             q.push(e);
60         }
61     }
62     return -1;
63 }
64 
65 int main()
66 {
67 
68     cin>>n>>m;
69     for(int i = 1; i<=n; i++)
70         scanf("%s",a[i]+1);
71 
72     for(int i = 1; i<=n; i++)
73         scanf("%s",b[i]+1);
74 
75     for(int i = 1; i<=n; i++)
76     for(int j = 1; j<=m; j++)
77     {
78         if(a[i][j]=='#' || b[i][j]=='#')
79             c[i][j] = '#';
80         else
81             c[i][j] = '.';
82     }
83 
84     int B = 0;
85     int t1 = bfs(1,1,a);//分别搜两幅图的最短路
86     int t2 = bfs(1,1,b);
87     if(t1 == t2 && t1 !=-1)//在最短路的前提下，再找两图合并的最短路是否存在并是否为原来的值
88     {
89         if( bfs(1,1,c)== t1 )
90             B = 1;
91     }
92 
93     if(B)
94         puts("YES");
95     else
96         puts("NO");
97 }

View Code