RT,#3是最小规模了,本地按这个规模拍了两万多组数据都没拍出错来,求调qwq
拆点做法,跑spfa
#include <cstdio>
#include <bitset>
#include <queue>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
inline int read() {
int s = 0;
char ch = getchar();
while (ch < 48 || ch > 57) {
ch = getchar();
}
while (ch > 47 && ch < 58) {
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return s;
}
inline int min(int a, int b) {
return a < b ? a : b;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
bitset<6750015> inq;
int n, m, dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, a[155][155], b[155][155], dis[6750015];
queue<int> q;
inline int turn(int x, int y, int z) {
return x * m * (n + m - 1) + y * (n + m - 1) + z;
}
void spfa(int s) {
for (int i = 0; i < n * m * (n + m - 1); i++) {
dis[i] = inf;
}
dis[s] = 0;
inq.set(s, 1);
q.push(s);
int u, v, x, y, z, tx, ty;
while (!q.empty()) {
u = q.front();
q.pop();
inq.set(u, 0);
z = u % (n + m - 1);
y = u / (n + m - 1) % m;
x = u / (n + m - 1) / m;
if (z) {
for (int i = 0; i < 4; i++) {
tx = x + dir[i][0];
ty = y + dir[i][1];
if (~tx && tx < n && ~ty && ty < m) {
v = turn(tx, ty, z - 1);
if (dis[u] < dis[v]) {
dis[v] = dis[u];
if (!inq.test(v)) {
q.push(v);
inq.set(v, 1);
}
}
}
}
v = turn(x, y, z - 1);
if (dis[u] < dis[v]) {
dis[v] = dis[u];
if (!inq.test(v)) {
q.push(v);
inq.set(v, 1);
}
}
}
if (z < b[x][y]) {
v = turn(x, y, b[x][y]);
if (dis[u] + a[x][y] < dis[v]) {
dis[v] = dis[u] + a[x][y];
if (!inq.test(v)) {
q.push(v);
inq.set(v, 1);
}
}
}
}
return;
}
int main() {
n = read();
m = read();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[i][j] = min(read(), max(i, n - i - 1) + max(j, n - j - 1));
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = read();
}
}
int x1, y1, x2, y2, x3, y3, dis12, dis13, dis21, dis23, dis31, dis32;
x1 = read() - 1;
y1 = read() - 1;
x2 = read() - 1;
y2 = read() - 1;
x3 = read() - 1;
y3 = read() - 1;
spfa(turn(x1, y1, 0));
dis12 = dis[turn(x2, y2, 0)];
dis13 = dis[turn(x3, y3, 0)];
spfa(turn(x2, y2, 0));
dis21 = dis[turn(x1, y1, 0)];
dis23 = dis[turn(x3, y3, 0)];
spfa(turn(x3, y3, 0));
dis31 = dis[turn(x1, y1, 0)];
dis32 = dis[turn(x2, y2, 0)];
char ch;
int ans = inf;
if (dis21 + dis31 < ans) {
ans = dis21 + dis31;
ch = 'X';
}
if (dis12 + dis32 < ans) {
ans = dis12 + dis32;
ch = 'Y';
}
if (dis13 + dis23 < ans) {
ans = dis13 + dis23;
ch = 'Z';
}
if (ans == inf) {
printf("NO\n");
}
else {
printf("%c\n%d\n", ch, ans);
}
return 0;
}