首先一步重要的转化是:找到一个起点和终点都能到达的中间状态,并分别求起点到中间、终点到中间的方案再合并起来输出。
那么现在的难点就在于如何寻找唯一确定的中间状态。
这是第二步重要的转化:考虑对这张地图进行编号,并把变形虫移动到编号最小的位置。
可以想到对于一个连通块直接用一次 dfs 编号,会产生一个类似于树的结构,这样移动过去显然最终状态是唯一确定的。
那么如何实现移动过程呢?发现移动相当于删除一个点,再添加一个点。
显然,在移动过程中变形虫不能断开,所以删除的不能是割点,而添加的点显然根据贪心是变形虫周围编号最小的点。
那么大致的算法思路就出来了:每次寻找一个编号最大非割点删掉,并在周围寻找编号最小空地添加进变形虫。
于是这题成了大模拟。
然而码力不够所以挂了好几发。
#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = N * N;
int n, m;
char mp[N][N];
int id[N][N], idx = 0;
int X[M], Y[M];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
void dfs(int x, int y) {
id[x][y] = ++idx;
X[idx] = x, Y[idx] = y;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
if (id[xx][yy] || mp[xx][yy] == 'X') continue;
dfs(xx, yy);
}
}
int dfn[N][N], low[N][N], tot = 0;
bool cut[N][N]; //是否为割点
int Max = 0;
void tarjan(int x, int y, int fx, int fy) {
dfn[x][y] = low[x][y] = ++tot;
int cut = 0;
if (fx > 0 && fy > 0) cut = 1;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m || mp[xx][yy] != '*') continue;
if (!dfn[xx][yy]) {
tarjan(xx, yy, x, y);
low[x][y] = min(low[x][y], low[xx][yy]);
if (dfn[x][y] <= low[xx][yy]) cut++;
} else if (!(xx == fx && yy == fy))
low[x][y] = min(low[x][y], dfn[xx][yy]);
}
if (cut < 2) Max = max(Max, id[x][y]);
}
struct node {
int sx, sy, ex, ey;
} ;
queue< node > ans1;
stack< node > ans2;
int solve(bool op) {
while (1) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) dfn[i][j] = low[i][j] = 0;
bool flag = 1; Max = tot = 0;
for (int i = 1; i <= n && flag; i++)
for (int j = 1; j <= m; j++)
if (mp[i][j] == '*') { tarjan(i, j, 0, 0), flag = 0; break; }
// cout << '\t' << X[Max] << ' ' << Y[Max] << endl;
// for (int i = 1; i <= n; i++) cout << mp[i] + 1 << endl;
mp[X[Max]][Y[Max]] = '.';
int Min = 0x3f3f3f3f;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++) {
if (mp[x][y] != '*') continue;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
if (mp[xx][yy] == '.') Min = min(Min, id[xx][yy]);
}
}
mp[X[Min]][Y[Min]] = '*';
if (Min == Max) break;
if (op == 1) ans1.push((node){X[Max], Y[Max], X[Min], Y[Min]});
else ans2.push((node){X[Max], Y[Max], X[Min], Y[Min]});
}
return Max;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("\n %s", mp[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!id[i][j] && mp[i][j] != 'X') dfs(i, j);
// for (int i = 1; i <= n; i++, puts(""))
// for (int j = 1; j <= m; j++) printf("%3d", id[i][j]); puts("");
int mid1 = solve(1);
for (int i = 1; i <= n; i++) scanf("\n %s", mp[i] + 1);
int mid2 = solve(0);
if (mid1 != mid2) puts("NO");
else {
puts("YES");
printf("%d\n", ans1.size() + ans2.size());
while (ans1.size()) {
node f = ans1.front(); ans1.pop();
printf("%d %d %d %d\n", f.sx, f.sy, f.ex, f.ey);
}
// puts("!");
while (ans2.size()) {
node f = ans2.top(); ans2.pop();
printf("%d %d %d %d\n", f.ex, f.ey, f.sx, f.sy);
}
}
return 0;
}
/*
5 8
******..
***X**..
***.**..
***X**..
******..
.******.
...X****
.*******
...X****
.******.
*/
/*
2 50
****...............X..............................
***..................X............................
...................X...........................***
.....................X........................****
*/