首页 > 代码库 > Codeforces Round #290 (Div. 2) B (dfs)
Codeforces Round #290 (Div. 2) B (dfs)
题目链接:http://codeforces.com/problemset/problem/510/B
题意:判断图中是否有某个字母成环
思路:直接dfs就好了,注意判断条件:若下一个字母与当前字母相同且已搜过,则存在满足题意的环
代码:
1 #include <bits/stdc++.h>
2 #define MAXN 60
3 using namespace std;
4
5 int mp[MAXN][MAXN], vis[MAXN][MAXN], m, n;
6 int dir[4][2]={0, 1, 1, 0, -1, 0, 0, -1};
7 bool flag=false;
8
9 void dfs(int x, int y, int direction){
10 if(flag){
11 return;
12 }
13 for(int i=0; i<4; i++){
14 int xx=x+dir[i][0];
15 int yy=y+dir[i][1];
16 if(xx>=0&&xx<n&&yy>=0&&yy<m){
17 if(i+direction!=3&&vis[xx][yy]&&mp[xx][yy]==mp[x][y]){ //***若下一个数字与当前数字相同且已经搜过,则存在满足题意的环,注意别往回的方向搜了
18 flag=true;
19 return;
20 }else if(!vis[xx][yy]&&mp[xx][yy]==mp[x][y]){
21 vis[xx][yy]=1;
22 dfs(xx, yy, i);
23 }
24 }
25 }
26 }
27
28 int main(void){
29 char ch;
30 cin >> n >> m;
31 for(int i=0; i<n; i++){
32 for(int j=0; j<m; j++){
33 cin >> ch;
34 mp[i][j]=ch-‘A‘+1;
35 }
36 }
37 for(int i=0; i<n; i++){
38 for(int j=0; j<m; j++){
39 if(!vis[i][j]){
40 vis[i][j]=1;
41 dfs(i, j, 0);
42 if(flag){
43 cout << "Yes" << endl;
44 return 0;
45 }
46 }
47 }
48 }
49 cout << "No" << endl;
50 return 0;
51 }
Codeforces Round #290 (Div. 2) B (dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。