help!!!
查看原帖
help!!!
1056402
hedgehog1211楼主2024/4/19 17:43
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
int n, m;
int f[N][N];
bool book[N][N];
int ans;
int sx, sy, ex, ey;
char d;

void dfs(char k, int x, int y, int t) {

	if (x == ex && y == ey) {
		ans = min(t, ans);
		return;
	}

	/*	if (t > ans)
			return;*/
	if (x < 1 || x > n + 1)
		return;
	if (y < 1 || y > m + 1)
		return;
	if (f[x][y] == 1 || book[x][y] == 1)
		return;
	book[x][y] = 1;
	if (k == 'W') {
		if (f[x][y - 1] != 1) {
			dfs(k, x, y - 1, t + 1);
			if (f[x][y - 2] != 1) {
				dfs(k, x, y - 2, t + 1);
				if (f[x][y - 3] != 1) {
					dfs(k, x, y - 3, t + 1);
				}
			}
		}
		dfs('S', x, y, t + 1);
		dfs('N', x, y, t + 1);
	}

	if (k == 'E') {
		if (f[x][y + 1] != 1) {
			dfs(k, x, y + 1, t + 1);
			if (f[x][y + 2] != 1) {
				dfs(k, x, y + 2, t + 1);
				if (f[x][y + 3] != 1) {
					dfs(k, x, y + 3, t + 1);
				}
			}
		}
		dfs('N', x, y, t + 1);
		dfs('S', x, y, t + 1);
	}

	if (k == 'S') {
		//	cout << "****" << endl;
		if (f[x + 1][y] != 1) {
			dfs(k, x + 1, y, t + 1);
			if (f[x + 2][y] != 1) {
				dfs(k, x + 2, y, t + 1);
				if (f[x + 3][y] != 1) {
					dfs(k, x + 3, y, t + 1);
				}
			}
		}
		dfs('E', x, y, t + 1);
		dfs('W', x, y, t + 1);
	}

	if (k == 'N') {
		if (f[x - 1][y] != 1) {
			dfs(k, x - 1, y, t + 1);
			if (f[x - 2][y] != 1) {
				dfs(k, x - 2, y, t + 1);
				if (f[x - 3][y] != 1) {
					dfs(k, x - 3, y, t + 1);
				}
			}
		}
		dfs('E', x, y, t + 1);
		dfs('W', x, y, t + 1);
	}


	book[x][y] = 0;
}



int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int a;
			cin >> a;
			if (a == 1) {
				f[i][j] = 1;
				f[i + 1][j] = 1;
				f[i][j + 1] = 1;
				f[i + 1][j + 1] = 1;
			}
		}
	}
	cin >> sx >> sy >> ex >> ey >> d;
	sx = sx + 1, sy = sy + 1, ex = ex + 1, ey = ey + 1;
	cout << sx << ' ' << sy;
	/*	for (int i = 1; i <= n + 1; i++) {
			for (int j = 1; j <= m + 1; j++) {
				cout << f[i][j] << ' ';
			}
			cout << endl;
		}*/
	ans = INT_MAX;
	dfs(d, sx, sy, 0);

	if (ans == INT_MAX)
		cout << -1;
	else
		cout << ans;


	return 0;
}

2024/4/19 17:43
加载中...