DFS-80分,求调,必关
查看原帖
DFS-80分,求调,必关
1101262
Ashankamiko楼主2025/1/9 22:38
#include <bits/stdc++.h>
using namespace std;

int o[214748364][2];
int dx[4] = {0, -1, 0, 1};

int dy[4] = {-1, 0, 1, 0};
int n, m, vis[15][15], s1, s2, e1, e2;
char maps[15][15];

bool DFS(int x, int y) {
	vis[x][y] = 1;
	if (e1 == x && y == e2)
		return true;
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if (tx >= 1 && tx <= n && ty > 0 && ty <= m && maps[tx][ty] != '0' && vis[tx][ty] == 0)
			if (DFS(tx, ty))
				return true;
	}
	return false;
}

void dfs(int x, int y, int h) {
	vis[x][y] = 1;
	if (x == e1 && y == e2) {
		cout << '(' << s1 << ',' << s2 << ")";
		for (int i = 0; i < h; i++)
			cout << "->(" << o[i][0] << "," << o[i][1] << ")";
		cout << endl;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if (tx >= 1 && tx <= n && ty > 0 && tx <= m && vis[tx][ty] == 0 && maps[tx][ty] == '1') {
			o[h][0] = tx, o[h][1] = ty;
			dfs(tx, ty, h + 1);
			vis[tx][ty] = 0;
		}
	}

}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> maps[i][j];
	cin >> s1 >> s2 >> e1 >> e2;
	if (!DFS(s1, s2)) {
		cout << "-1";
		return 0;
	}
	memset(vis, 0, sizeof(vis));
	vis[s1][s2]=1;
	dfs(s1, s2, 0);
	return 0;
}

啊啊啊为什么80分,4个WA也不懂为什么WA

2025/1/9 22:38
加载中...