帮我朋友问一下“dfs 样例都没出现问题,感谢哪位大佬帮帮忙”
  • 板块灌水区
  • 楼主tiancai_1234
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/30 22:12
  • 上次更新2024/3/31 09:02:40
查看原帖
帮我朋友问一下“dfs 样例都没出现问题,感谢哪位大佬帮帮忙”
1207389
tiancai_1234楼主2024/3/30 22:12

他说这题能用dfs,他看有些人是这么写的,结果wa了

#include<iostream>
#include<string>
using namespace std;
int via[100][100], n, m, x, y, x1, y3, ans = 1000000;
string s[10];
int a[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int in(int x, int y) {
	return 0 <= x && x < n && y < m && y >= 0;
}
bool dfs(int x, int y, int step) {

	if (x == x1 && y == y3) {
		if (step < ans) {
			ans = step;
		}
		return true;
	}
	via[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int x2 = x + a[i][0];
		int y2 = y + a[i][1];
		if (in(x2, y2) && !via[x2][y2] && s[x2][y2] == '.') {
			dfs(x2, y2, step + 1);
		}
	}via[x][y] = 0;
	return false;
}
int main() {
	cin >> n >> m >> x >> y >> x1 >> y3;
	x -= 1;
	y -= 1;
	x1 -= 1;
	y3 -= 1;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	dfs(x, y, 0);
	cout << ans;
	return 0;
}
``` cpp
2024/3/30 22:12
加载中...