codeforces 475 B. Strongly Connected City
http://codeforces.com/problemset/status 题意:n行m列的道路网络。共n*m条道路。每条道路都是单向的.问从任何一个路口出发能否到达其他的任何一个路口。
思路:需要注意的是。我从A点能到达B点,不代表B也能到达A.也就是说,某些点满足可以遍历所有点是不够的,只有当所有点都满足才可以。
/* ***********************************************
Author :111qqz
Created Time :2015年12月07日 星期一 08时55分48秒
File Name :code/cf/problem/475B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=25;
7int n,m;
8bool vis[N][N];
9char hor[N],ver[N];
1bool direrror (char ch,int d)
2{
3 if (ch=='v'&&d==3) return true;
4 if (ch=='^'&&d==0) return true;
if (ch=='<'&&d==2) return true;
if (ch=='>'&&d==1) return true;
return false;
}
1bool ok ( int x,int y)
2{
3 if (x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]) return true;
4 return false;
5}
1void dfs ( int x,int y)
2{
3 vis[x][y] = true;
4 // cout<<"x:"<<x<<" y:"<<y<<endl;
5 for ( int i = 0 ; i < 4 ; i++)
6 {
7 if (direrror(hor[x],i)) continue;
8 if (direrror(ver[y],i)) continue;
1 int nx = x + dx4[i];
2 int ny = y + dy4[i];
3 if (ok(nx,ny))
4 {
5 dfs(nx,ny);
6 }
7 }
8}
1bool solve ( int x,int y)
2{
3 ms(vis,false);
4 dfs(x,y);
5 for ( int i = 0 ; i < n ; i++)
6 for ( int j = 0 ; j < m; j ++)
7 if (!vis[i][j]) return false;
8 return true;
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("code/in.txt","r",stdin);
6 #endif
1 cin>>n>>m; //注意题目要求是从任意一点都可以到达其他任何点。
2 for ( int i = 0 ; i < n ; i ++) cin>>hor[i];
3 for ( int i = 0 ; i < m ; i ++) cin>>ver[i];
1 int cnt = 0 ;
2 bool ok = true;
3 for ( int i = 0 ; i< n ; i++)
4 for ( int j = 0 ;j < m; j++)
5 if (!solve(i,j))
6 {
7 ok = false;
8 break;
9 }
10// cout<<"cnt:"<<cnt<<endl;
11 if (ok)
12 {
13 puts("YES");
14 }
15 else
16 {
17 puts("NO");
18 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}