一WA一RE, 求助各位大佬
查看原帖
一WA一RE, 求助各位大佬
206463
烬丶星落少年楼主2020/11/26 16:06
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 352
#define MAXM 17
using namespace std;

int n, m;
int con1, con2, dis;
int s[MAXN][MAXN], cnt;
bool kinds[MAXN][MAXN];
int sx, sy, tx, ty;
int sp[8][2] = {1, 1, 1, 0, 1, -1, 0, 1, 0, -1, -1, 1, -1, 0, -1, -1};
int sps[4][2];
bool vis[MAXN][MAXN][MAXM][MAXM];
struct Node {
	int x, y, c1, c2, ans;
};
queue<Node> que;

bool Sure(int x, int y) {
	return !kinds[x][y] && x > 0 && x <= n && y > 0 && y <= m;
}

int main() {
	scanf("%d%d%d%d%d", &n, &m, &con1, &con2, &dis);
	sps[0][0] = dis;sps[1][0] = -dis;
	sps[2][1] = dis;sps[3][1] = -dis;
	string str;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> str;
			if (str[0] == 'S') {
				sx = i; sy = j;
			}
			if (str[0] == 'T') {
				tx = i; ty = j;
			}
			if (str[0] >= '0' && str[0] <= '9') {
				for (int l = 0; l < str.size(); l++)
					s[i][j] = s[i][j] * 10 + str[l] - '0';
				kinds[i][j] = 1;
			}
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			s[i][j] = max(s[i][j], max(s[i - 1][j], s[i][j - 1]) - 1);
	for (int i = n; i >= 1; i--)
		for (int j = m; j >= 1; j--)
			s[i][j] = max(s[i][j], max(s[i + 1][j], s[i][j + 1]) - 1);
	Node got;
	que.push(Node{sx, sy, 0, 0, 0});
	while(que.size()) {
		got = que.front(); que.pop();
		got.ans++;
		for (int i = 0; i < 8; i++) {
			int vx = got.x + sp[i][0];
			int vy = got.y + sp[i][1];
			if (!s[vx][vy] && vx == tx && vy == ty) {
				cout << got.ans << ' ' << got.c1 << ' ' << got.c2 << '\n';
				return 0;
			}
			if (Sure(vx, vy) && !s[vx][vy] && !vis[vx][vy][got.c1][got.c2]) {
				vis[vx][vy][got.c1][got.c2] = 1;
				que.push(Node{vx, vy, got.c1, got.c2, got.ans});
			}
		}
		if (got.c2 < con2)
			for (int i = 0; i < 4; i++) {
				int vx = got.x + sps[i][0];
				int vy = got.y + sps[i][1];
				if (!s[vx][vy] && vx == tx && vy == ty) {
					cout << got.ans << ' ' << got.c1 << ' ' << got.c2 + 1 << '\n';
					return 0;
				}
				if (Sure(vx, vy) && !s[vx][vy] && !vis[vx][vy][got.c1][got.c2 + 1]) {
					vis[vx][vy][got.c1][got.c2 + 1] = 1;
					que.push(Node{vx, vy, got.c1, got.c2 + 1, got.ans});
				}
			}
		if (got.c1 < con1) {
			for (int i = 0; i < 8; i++) {
				int vx = got.x + sp[i][0];
				int vy = got.y + sp[i][1];
				if (vx == tx && vy == ty) {
					cout << got.ans << ' ' << got.c1 + 1 << ' ' << got.c2 << '\n';
					return 0;
				}
				if (Sure(vx, vy) && s[vx][vy] && !vis[vx][vy][got.c1 + 1][got.c2]) {
					vis[vx][vy][got.c1 + 1][got.c2] = 1;
					que.push(Node{vx, vy, got.c1 + 1, got.c2, got.ans});
				}
			}
			if (got.c2 < con2)
				for (int i = 0; i < 4; i++) {
					int vx = got.x + sps[i][0];
					int vy = got.y + sps[i][1];
					if (vx == tx && vy == ty) {
						cout << got.ans << ' ' << got.c1 + 1 << ' ' << got.c2 + 1 << '\n';
						return 0;
					}
					if (Sure(vx, vy) && s[vx][vy] && !vis[vx][vy][got.c1 + 1][got.c2 + 1]) {
						vis[vx][vy][got.c1 + 1][got.c2 + 1] = 1;
						que.push(Node{vx, vy, got.c1 + 1, got.c2 + 1, got.ans});
					}
				}
		}
	}
	cout << -1 << '\n';
	return 0;
}
2020/11/26 16:06
加载中...