首页 > 代码库 > codeforces B. Strongly Connected City(dfs水过)

codeforces B. Strongly Connected City(dfs水过)

2024-07-25 17:44:10   221人阅读

题意：有横向和纵向的街道，每个街道只有一个方向，垂直的街道相交会产生一个节点，这样每个节点都有两个方向，
问是否每一个节点都可以由其他的节点到达....
思路：规律没有想到，直接爆搜！每一个节点dfs一次，记录每个节节点被访问的次数！如果每个节点最终的访问次数
和所有节点的数目相同，则输出“YES", 否则输出”NO“

 1 #include <queue> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7  8 using namespace std; 9 10 char s1[25], s2[25];11 int vis[25][25];12 int cnt[25][25];13 int n, m;14 15 void dfs(int x, int y){16     if(x<1 || x>n || y<1 || y>m || vis[x][y]) return;17     ++cnt[x][y];18     vis[x][y] = 1;19     if(s1[x] == ‘<‘)20         dfs(x, y-1);21     else dfs(x, y+1);22 23     if(s2[y] == ‘v‘)24         dfs(x+1, y);25     else dfs(x-1, y);26 }27 28 int main(void)29 {30     scanf("%d%d", &n, &m);31     scanf("%s%s", s1+1, s2+1);32 33     for(int i=1; i<=n; ++i)34         for(int j=1; j<=m; ++j){35             memset(vis, 0, sizeof(vis));36             dfs(i, j);37         }38     int s = n*m;39     for(int i =1; i<=n; ++i)40             for(int j=1; j<=m; ++j)41                 if(cnt[i][j] != s){42                     cout<<"NO"<<endl;43                     return 0;44                 }45     cout<<"YES"<<endl;46     return 0;47 }
View Code

 

codeforces B. Strongly Connected City(dfs水过)


联系
我们