Codeforces 475 B Strongly Connected City【DFS】

题意:给出n行m列的十字路口,<代表从东向西,>从西向东,v从北向南,^从南向北,问在任意一个十字路口是否都能走到其他任意的十字路口

四个方向搜,搜完之后,判断每个点能够访问的点的数目是否相同,相同的话则说明可以到达任意点

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
const int INF = 0x7fffffff;
const int maxn=;
char s1[maxn],s2[maxn];
int cnt[maxn][maxn],vis[maxn][maxn];
int n,m; void dfs(int x,int y){
if(x<||x>n||y<||y>m) return;
if(vis[x][y]) return;
vis[x][y]=;
cnt[x][y]++;
if(s1[x]=='>') dfs(x,y+);
if(s1[x]=='<') dfs(x,y-);
if(s2[y]=='v') dfs(x+,y);
if(s2[y]=='^') dfs(x-,y);
} int main(){
int i,j;
scanf("%d %d",&n,&m);
cin>>(s1+);
cin>>(s2+); memset(cnt,,sizeof(cnt)); for(i=;i<=n;i++){
for(j=;j<=m;j++){
memset(vis,,sizeof(vis));
dfs(i,j);
}
} //for(i=1;i<=n;i++){
// for(j=1;j<=m;j++)
// printf("cnt[%d][%d]=%d\n",i,j,cnt[i][j]);
//} for(i=;i<=n;i++){
for(j=;j<=m;j++){
if(cnt[i][j]!=cnt[][]){
printf("NO\n");
return ;
}
}
} printf("YES\n");
return ;
}

后来搜题解发现还有用强连通分量做的,还有用floyd做的= =

上一篇:局部权重线性回归(Locally weighted linear regression)


下一篇:.NET使用ICSharpCode.SharpZipLib压缩/解压文件