#include using namespace std; const int maxN = 55; struct Point { int x, y; }; int n, m; int initMat[maxN][maxN], finMat[maxN][maxN]; int dist[maxN][maxN]; Point prv[maxN][maxN]; bool used[maxN][maxN]; string str; int dlin[] = {-1, 1, 0, 0}; int dcol[] = {0, 0, -1, 1}; queue q; bool InBounds(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; } void dfs(int x, int y, int mat[maxN][maxN], int otherMat[maxN][maxN], vector &v) { if (!otherMat[x][y]){ v.push_back({x, y}); } used[x][y] = 1; for (int k = 0; k < 4; k++) { int nx = x + dlin[k]; int ny = y + dcol[k]; if (InBounds(nx, ny) && mat[nx][ny] == 1 && !used[nx][ny]) { dfs(nx, ny, mat, otherMat, v); } } } void moveAmoebaConnected(Point suprapus) { vector s, d; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = 0; } } dfs(suprapus.x, suprapus.y, initMat, finMat, s); reverse(s.begin(), s.end()); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = 0; } } dfs(suprapus.x, suprapus.y, finMat, initMat, d); assert(s.size() == d.size()); cout << "YES\n" << s.size() << '\n'; for (int i = 0; i < (int) s.size(); i++) { cout << s[i].x << ' ' << s[i].y << ' ' << d[i].x << ' ' << d[i].y << '\n'; } } void Lee() { while (!q.empty()) { Point curr = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int nx = curr.x + dlin[k]; int ny = curr.y + dcol[k]; if (InBounds(nx, ny) && !used[nx][ny] && initMat[nx][ny] != -1) { q.push({nx, ny}); prv[nx][ny] = curr; used[nx][ny] = 1; if (finMat[nx][ny] == 1) { return; } } } } } void moveAmoebaOnChain() { Lee(); Point last; bool ok = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!ok && finMat[i][j] == 1 && used[i][j]) { last = {i, j}; ok = 1; } } } if (!ok) { cout << "NO\n"; return; } vector chain; Point initP = {0, 0}, finP; while (last.x != 0 && last.y != 0) { chain.push_back(last); last = prv[last.x][last.y]; } reverse(chain.begin(), chain.end()); assert(initMat[chain[0].x][chain[0].y] == 1); assert(finMat[chain.back().x][chain.back().y] == 1); vector s, d; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = 0; } } dfs(chain[0].x, chain[0].y, initMat, finMat, s); reverse(s.begin(), s.end()); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { used[i][j] = 0; } } dfs(chain.back().x, chain.back().y, finMat, initMat, d); for (int i = 1; i < chain.size() - 1; i++) { s.push_back(chain[i]); } reverse(d.begin(), d.end()); for (int i = chain.size() - 2; i > 0; i--) { d.push_back(chain[i]); } reverse(d.begin(), d.end()); cout << "YES\n" << s.size() << '\n'; assert(s.size() == d.size()); for (int i = 0; i < s.size(); i++) { cout << s[i].x << ' ' << s[i].y << ' ' << d[i].x << ' ' << d[i].y << '\n'; } } int main() { #ifdef HOME freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #endif // HOME cin.tie(NULL); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> str; for (int j = 1; j <= m; j++) { if (str[j - 1] == 'X') { initMat[i][j] = -1; } if (str[j - 1] == '*') { initMat[i][j] = 1; used[i][j] = 1; q.push({i, j}); } } } for (int i = 1; i <= n; i++) { cin >> str; for (int j = 1; j <= m; j++) { if (str[j - 1] == 'X') { finMat[i][j] = -1; } if (str[j - 1] == '*') { finMat[i][j] = 1; } } } Point suprapus; bool ok = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (initMat[i][j] == 1 && finMat[i][j] == 1) { ok = 1; suprapus = {i, j}; } } } if (!ok) { moveAmoebaOnChain(); } else { moveAmoebaConnected(suprapus); } return 0; }