475B Strongly Connected City

本文主要是介绍475B Strongly Connected City，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Imagine a city with n horizontal streets crossing m vertical 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.

$\text{[math]}$

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 integers n and m, (2 ≤ n, m ≤ 20), denoting the number of horizontal streets and the number of vertical streets.

The second line contains a string of length n, made of characters '<' and '>', denoting direction of each horizontal street. If the i-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 length m, made of characters '^' and 'v', denoting direction of each vertical street. If the i-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.

题目意思：

画n条水平线，m条垂直线，有n*m个交点，然后每条直线只给定一个通行方向，问所有交点能不能走通。

后来看了一种方法，现在添加进去，如果外围是顺时针或则逆时针，则YES

分析：刚开始想是不是博弈，想到每条线的方向有影响，就不考虑了。后来，看到数据范围比较小，问能不能走通嘛，floyd求出所有交点的最小距离。因此，这题就转成了图去。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define INF 10000
#define eps 1e-6
#define pb push_back
#define pf printf
#define sf scanf
#define si(n) sf("%d",&n)
#define pi(n) pf("%d\n",n)
#define ms memset
#define bk break
#define rt return
#define ct continue
#define LL long long
#define REP0(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define mp(x,y) make_pair((x),(y))
#define maxn 500
#define MOD
#define db double
#define op operator
#define PI acos(-1)
using namespace std;
int n,m;
int mapt[maxn][maxn];
int num[30][30];
void init(){REP(i,1,n*m){REP(j,1,n*m){mapt[i][j]=INF;}mapt[i][i]=0;}
}
bool judge(){REP(i,1,n*m)REP(j,1,n*m)if(mapt[i][j]==INF)rt false;rt true;
}
void floyd(){for(int k=1;k<=n*m;k++){for(int i=1;i<=n*m;i++){for(int j=1;j<=n*m;j++){if(mapt[i][j]>mapt[i][k]+mapt[k][j] )mapt[i][j]=mapt[i][k]+mapt[k][j];}}}
}
void out(){REP(i,1,n*m){REP(j,1,n*m){cout<<mapt[i][j]<<" ";}cout<<endl;}cout<<endl;
}
int main(){#ifdef ACBangfreopen("in.txt","r",stdin);#endifwhile(~sf("%d%d",&n,&m)){init();
//out();int cnt=1,a,b;REP(i,1,n)REP(j,1,m)num[i][j]=cnt++;char s[100];sf("%s",s);REP(i,1,n){if(s[i-1]=='>'){for(int t=1;t<=m;t++){for(int k=t+1;k<=m;k++){a=num[i][t];b=num[i][k];mapt[a][b]=1;}}}else {for(int t=1;t<=m;t++){for(int k=t+1;k<=m;k++){a=num[i][t];b=num[i][k];mapt[b][a]=1;}}}}
//out();sf("%s",s);REP(j,1,m){if(s[j-1]=='^'){for(int t=1;t<=n;t++){for(int k=t+1;k<=n;k++){a=num[t][j];b=num[k][j];mapt[b][a]=1;}}}else {for(int t=1;t<=n;t++){for(int k=t+1;k<=n;k++){a=num[t][j];b=num[k][j];mapt[a][b]=1;}}}}
//out();floyd();
//out();if(judge()==true)puts("YES");else puts("NO");}rt 0;
}

这篇关于475B Strongly Connected City的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！