dfs超时,如何优化
查看原帖
dfs超时,如何优化
1147820
anFine3ks楼主2023/12/21 23:20
#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[502][502];
bool ans;
bool a[502][502];

void dfs(int x, int y) {
	if (x > n || y > m || x <= 0 || y <= 0) {
		return;
	}
	if (s[x][y] == 'g') {
		ans = true;
		return;
	}
	if (a[x][y]) {
		return;
	}
	if (!a[x][y]) {
		a[x][y] = true;
		dfs(x + 1, y);
		dfs(x - 1, y);
		dfs(x, y + 1);
		dfs(x, y - 1);
		a[x][y] = false;
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int x = 0, y = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
			if (s[i][j] == 's') {
				x = i, y = j;
			}
			if (s[i][j] == '#') {
				a[i][j] = true;
			}
		}
	}
	dfs(x, y);
	if (ans) {
		cout << "Yes";
	} else
		cout << "No";
	return 0;
}
2023/12/21 23:20
加载中...