裂开了呀,找不到错误,第一次写dfs的题目,请大佬们帮帮忙,看下
查看原帖
裂开了呀,找不到错误,第一次写dfs的题目,请大佬们帮帮忙,看下
419652
MOXCOOT楼主2021/2/8 20:13
#include<iostream>
#define NUM 500
using namespace std;
char str[] = "yizhong";
char a[NUM][NUM];
int s[NUM][NUM] = { 0 };
int dx[] = { -1,-1,-1,0,0,1,1,1,0 };
int dy[] = { -1,0,1,1,-1,-1,0,1,0 };
bool dfs(int i, int j, int next) {                             
	//i和j是指'y'字符所在的坐标,从这里开始搜索
	
	if (next >= 8) {                                           
	//到这个时候已经搜索到了最后一个
		return 1;
	}
	if (a[i][j] == str[next]) {
		for (int a = 0; a < 10; a++) {                         
			//依次按照dx[]和dy[]的方向进行搜索
			if (dfs(i + dx[a], j + dy[a], next + 1)) {
				s[i][j] = 1;                                   
			//如果成功连成str[]则将所有坐标依次标为 1
				return 1;
			}
		}
	}
	else
		return 0;
}

int main() {
	//输入
	int n;
	cin >> n;
	int ch[NUM][2];
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char x;
			cin >> x;
			a[i][j] = x;
			if (x == 'y') {                                 
				//如果遇到'y'则记录下他的位置
				ch[cnt][0] = i;
				ch[cnt][1] = j;
				cnt++;
			}
		}
	}
	for (int i = 0; i < cnt; i++) {                        
		//对于每个'y'进行搜索
		dfs(ch[i][0], ch[i][1], 0);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (s[i][j])                                   
				//被标记的位置输出原字符
				cout << a[i][j];
			else                                           
				//未被标记的字符则输出'*'
				cout << '*';
		}
		cout << endl;
	}
}
2021/2/8 20:13
加载中...