C++ dfs 92pts 求助
查看原帖
C++ dfs 92pts 求助
733515
LikablePie79015楼主2024/6/30 20:54

#12 WA

实在想不到哪里有问题了()

#include <iostream>
using namespace std;

int n, m;
int a[10][10];
int vis[10][10];
int sx, sy, ex, ey;
int antiTLE;
int minn = 0x7fffffff;

int dx[] = {0, -1, 0, 1, 0};
int dy[] = {0, 0, -1, 0, 1};

void dfs(int x, int y, int heap, int time) {
	if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] && !vis[x][y] && heap) {
		antiTLE++;
		if (antiTLE > 114514) {
			return ;
		}
		if (x == ex && y == ey) {
			minn = min(minn, time);
			return ;
		}
		if (a[x][y] == 4) {
			heap = 6;
		}
		vis[x][y] = 1;
		for (int i = 1; i <= 4; i++) {
			dfs(x + dx[i], y + dy[i], heap - 1, time + 1);
		}
		vis[x][y] = 0;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 2) {
				sx = i;
				sy = j;
			}
			if (a[i][j] == 3) {
				ex = i;
				ey = j;
			}
		}
	}

	dfs(sx, sy, 6, 0);

	if (minn == 0x7fffffff) {
		cout << -1;
	} else {
		cout << minn;
	}
	return 0;
}
2024/6/30 20:54
加载中...