B. Strongly Connected City
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Imagine a city withnhorizontal streets crossingmvertical streets, forming an(n-1)×(m-1)grid. In order to increase the traffic flow, mayor of the city has decided to make each street one way. This means in each horizontal street, the traffic moves only from west to east or only from east to west. Also, traffic moves only from north to south or only from south to north in each vertical street. It is possible to enter a horizontal street from a vertical street, or vice versa, at their intersection.
The mayor has received some street direction patterns. Your task is to check whether it is possible to reach any junction from any other junction in the proposed street direction pattern.
Input
The first line of input contains two integersnandm, (2≤n,m≤20), denoting the number of horizontal streets and the number of vertical streets.
The second line contains a string of lengthn, made of characters ‘<‘ and ‘>’, denoting direction of each horizontal street. If thei-th character is equal to ‘<‘, the street is directed from east to west otherwise, the street is directed from west to east. Streets are listed in order from north to south.
The third line contains a string of lengthm, made of characters ‘^’ and ‘v’, denoting direction of each vertical street. If thei-th character is equal to ‘^’, the street is directed from south to north, otherwise the street is directed from north to south. Streets are listed in order from west to east.
Output
If the given pattern meets the mayor’s criteria, print a single line containing "YES", otherwise print a single line containing "NO".
Sample test(s)
input
3 3><>v^v
output
NO
input
4 6<><>v^v^v^
output
YES
Note
The figure above shows street directions in the second sample test case.
题解：这一题可以直接广搜加记忆化，每次广搜成功后，从根到所有的点都是合法的。这样对于每两个点都搜一次，如果有不能到达的点就直接输出NO，可以到达的点就记录，所有点都搜完了就输出YES。（因为没有点是不可到达的）。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;char s1[25],s2[25];int x[25],y[25],d[25][25][25][25],k,f[25][25],n,m;int l1,l2,h,t;struct queue{int x,y;};struct queue q[405];void check(int x,int y){if (!f[x][y] && x<=n && y<=m && x>0 && y>0){q[t].x=x; q[t].y=y;t++;f[x][y]=1;}}int bfs(int x1,int y1,int x2,int y2){memset(f,0,sizeof(f));memset(q,0,sizeof(q));h=0;t=0;q[t].x=x1; q[t].y=y1; t++;while (h!=t){if (q[h].x==x2 && q[h].y==y2){for (int i=0;i<t;i++) d[x1][x2][q[i].x][q[i].y]=1;return 1;}check(q[h].x,x[q[h].x]+q[h].y);check(y[q[h].y]+q[h].x,q[h].y);h++;}return 0;}int main(){scanf("%d%d",&n,&m);scanf("%s",s1); scanf("%s",s2);l1=strlen(s1); l2=strlen(s2);for (int i=0;i<l1;i++) if (s1[i]=='<') x[i+1]=-1;else x[i+1]=1;for (int i=0;i<l2;i++) if (s2[i]=='^') y[i+1]=-1;else y[i+1]=1;for (int x1=1;x1<=n;x1++)for (int y1=1;y1<=m;y1++)for (int x2=1;x2<=n;x2++)for (int y2=1;y2<=m;y2++){k=0;if ((x1!=x2 || y1!=y2)&&(!d[x1][y1][x2][y2])){k=bfs(x1,y1,x2,y2);if (k) d[x1][y1][x2][y2]=1;else{cout <<"NO"<<endl;return 0;}}}cout <<"YES"<<endl;return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，什么天荒地老，什么至死不渝。都只是锦上添花的借口…
