DFS求助
查看原帖
DFS求助
857626
_RainCappuccino_楼主2023/5/29 14:56
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN = 2000 + 5;
int n, m;
int r, c;
int p, q;
int ans;
char map[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool can(int h, int l) {
	if (h < n && h >= 0 && l >= 0 && l < m && map[h][l] != '*') {
		return 1;
	}
	return 0;
}
void dfs(int h, int l, int cz, int cr) {
//	cout << h << " " << l << "\n";
	int x = h, y = l + 1;
	if (can(x, y) && !vis[x][y] && cr < q) {
//		cout << "right:" << h << " " << l << "->" << x << " " << y << endl;
		vis[x][y] = 1;
		dfs(x, y, cz, cr + 1);
	}
	x = h, y = l - 1;
	if (can(x, y) && !vis[x][y] && cz < p) {
//		cout << "left:" << h << " " << l << "->" << x << " " << y << endl;
		vis[x][y] = 1;
		dfs(x, y, cz + 1, cr);
	}
	x = h + 1, y = l;
	if (can(x, y) && !vis[x][y]) {
//		cout << "up:" << h << " " << l << "->" << x << " " << y << endl;
		vis[x][y] = 1;
		dfs(x, y, cz, cr);
	}
	x = h - 1, y = l;
	if (can(x, y) && !vis[x][y]) {
//		cout << "down:" << h << " " << l << "->" << x << " " << y << endl;
		vis[x][y] = 1;
		dfs(x, y, cz, cr);
	}
}
void bfs(){
	
}
signed main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	cin >> r >> c;
	r--, c--;
	cin >> p >> q;
	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}
	vis[r][c] = 1;
	dfs(r, c, 0, 0);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (vis[i][j]) ans++;
	cout << ans << endl;
	return 0;
}
2023/5/29 14:56
加载中...