TLE on #18

提交记录

代(die)码

#include <bits/stdc++.h>
using namespace std;
const int N = 360;
const int M = 16;
const int INF = 1e9;
struct State {
	int x, y, u1, u2;
	int time, sum, s;
	bool operator<(const State& other) const {
		if (time != other.time) return time > other.time;
		if (sum != other.sum) return sum > other.sum;
		return s > other.s;
	}
};
int n, m, c1, c2, dist;
int sx, sy, tx, ty;
bool person[N][N];
bool cov[N][N];
int best_time[N][N][M][M];
int best_sum[N][N][M][M];
int best_s[N][N][M][M];
const int dx8[] = {-1, 0, 1, 0, -1, 1, 1, -1};
const int dy8[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dx4[] = {1, -1, 0, 0};
const int dy4[] = {0, 0, 1, -1};
bool exist(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);	
	cin >> n >> m >> c1 >> c2 >> dist;
	vector<vector<string> > grid(n+1, vector<string>(m+1));
	vector<vector<int> > guard_k(n+1, vector<int>(m+1, 0));
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> grid[i][j];
			if (grid[i][j] == "S") {
				sx = i;
				sy = j;
			} else if (grid[i][j] == "T") {
				tx = i;
				ty = j;
			} else if (grid[i][j] != ".") {
				person[i][j] = true;
				guard_k[i][j] = stoi(grid[i][j]);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (person[i][j]) {
				int k = guard_k[i][j];
				int min_x = max(1, i - (k - 1));
				int max_x = min(n, i + (k - 1));
				for (int x = min_x; x <= max_x; ++x) {
					int remaining = (k - 1) - abs(x - i);
					int min_y = max(1, j - remaining);
					int max_y = min(m, j + remaining);
					for (int y = min_y; y <= max_y; ++y) {
						if (x != i || y != j) {
							cov[x][y] = true;
						}
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			for (int u1 = 0; u1 <= c1; ++u1) {
				for (int u2 = 0; u2 <= c2; ++u2) {
					best_time[i][j][u1][u2] = INF;
					best_sum[i][j][u1][u2] = INF;
					best_s[i][j][u1][u2] = INF;
				}
			}
		}
	}
	priority_queue<State> pq;
	best_time[sx][sy][c1][c2] = 0;
	best_sum[sx][sy][c1][c2] = 0;
	best_s[sx][sy][c1][c2] = 0;
	pq.push({sx, sy, c1, c2, 0, 0, 0});
	while (!pq.empty()) {
		State curr = pq.top();
		pq.pop();	
		if (curr.time > best_time[curr.x][curr.y][curr.u1][curr.u2]) continue;
		if (curr.time == best_time[curr.x][curr.y][curr.u1][curr.u2] && curr.sum > best_sum[curr.x][curr.y][curr.u1][curr.u2]) continue;
		if (curr.time == best_time[curr.x][curr.y][curr.u1][curr.u2] && curr.sum == best_sum[curr.x][curr.y][curr.u1][curr.u2] && curr.s > best_s[curr.x][curr.y][curr.u1][curr.u2]) continue;
		if (curr.x == tx && curr.y == ty) {
			cout << curr.time << " " << curr.s << " " << (curr.sum - curr.s) << endl;
			return 0;
		}		
		for (int d = 0; d < 8; ++d) {
			int nx = curr.x + dx8[d];
			int ny = curr.y + dy8[d];
			if (!exist(nx, ny) || person[nx][ny] || cov[nx][ny]) continue;	
			int new_time = curr.time + 1;
			int new_sum = curr.sum;
			int new_s = curr.s;
			int nu1 = curr.u1;
			int nu2 = curr.u2;
			if (new_time < best_time[nx][ny][nu1][nu2] || (new_time == best_time[nx][ny][nu1][nu2] && new_sum < best_sum[nx][ny][nu1][nu2]) || (new_time == best_time[nx][ny][nu1][nu2] && new_sum == best_sum[nx][ny][nu1][nu2] && new_s < best_s[nx][ny][nu1][nu2])) {
				best_time[nx][ny][nu1][nu2] = new_time;
				best_sum[nx][ny][nu1][nu2] = new_sum;
				best_s[nx][ny][nu1][nu2] = new_s;
				pq.push({nx, ny, nu1, nu2, new_time, new_sum, new_s});
			}
		}
		if (curr.u1 > 0) {
			for (int d = 0; d < 8; ++d) {
				int nx = curr.x + dx8[d];
				int ny = curr.y + dy8[d];
				if (!exist(nx, ny) || person[nx][ny]) continue;		
				int new_time = curr.time + 1;
				int new_sum = curr.sum + 1;
				int new_s = curr.s + 1;
				int nu1 = curr.u1 - 1;
				int nu2 = curr.u2;
				if (new_time < best_time[nx][ny][nu1][nu2] || (new_time == best_time[nx][ny][nu1][nu2] && new_sum < best_sum[nx][ny][nu1][nu2]) || (new_time == best_time[nx][ny][nu1][nu2] && new_sum == best_sum[nx][ny][nu1][nu2] && new_s < best_s[nx][ny][nu1][nu2])) {
					best_time[nx][ny][nu1][nu2] = new_time;
					best_sum[nx][ny][nu1][nu2] = new_sum;
					best_s[nx][ny][nu1][nu2] = new_s;
					pq.push({nx, ny, nu1, nu2, new_time, new_sum, new_s});
				}
			}
		}
		if (curr.u2 > 0) {
			for (int d = 0; d < 4; ++d) {
				int nx = curr.x + dx4[d] * dist;
				int ny = curr.y + dy4[d] * dist;
				if (!exist(nx, ny) || person[nx][ny] || cov[nx][ny]) continue;		
				int new_time = curr.time + 1;
				int new_sum = curr.sum + 1;
				int new_s = curr.s;
				int nu1 = curr.u1;
				int nu2 = curr.u2 - 1;
				if (new_time < best_time[nx][ny][nu1][nu2] || (new_time == best_time[nx][ny][nu1][nu2] && new_sum < best_sum[nx][ny][nu1][nu2]) || (new_time == best_time[nx][ny][nu1][nu2] && new_sum == best_sum[nx][ny][nu1][nu2] && new_s < best_s[nx][ny][nu1][nu2])) {
					best_time[nx][ny][nu1][nu2] = new_time;
					best_sum[nx][ny][nu1][nu2] = new_sum;
					best_s[nx][ny][nu1][nu2] = new_s;
					pq.push({nx, ny, nu1, nu2, new_time, new_sum, new_s});
				}
			}
		}
		if (curr.u1 > 0 && curr.u2 > 0) {
			for (int d = 0; d < 4; ++d) {
				int nx = curr.x + dx4[d] * dist;
				int ny = curr.y + dy4[d] * dist;
				if (!exist(nx, ny) || person[nx][ny]) continue;		
				int new_time = curr.time + 1;
				int new_sum = curr.sum + 2;
				int new_s = curr.s + 1;
				int nu1 = curr.u1 - 1;
				int nu2 = curr.u2 - 1;
				if (new_time < best_time[nx][ny][nu1][nu2] || (new_time == best_time[nx][ny][nu1][nu2] && new_sum < best_sum[nx][ny][nu1][nu2]) || (new_time == best_time[nx][ny][nu1][nu2] && new_sum == best_sum[nx][ny][nu1][nu2] && new_s < best_s[nx][ny][nu1][nu2])) {
					best_time[nx][ny][nu1][nu2] = new_time;
					best_sum[nx][ny][nu1][nu2] = new_sum;
					best_s[nx][ny][nu1][nu2] = new_s;
					pq.push({nx, ny, nu1, nu2, new_time, new_sum, new_s});
				}
			}
		}
	}	
	cout << -1 << endl;
	return 0;
}