#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define pii pair #define vi vector #define vpii vector #define SZ(x) ((int)(x.size())) #define fi first #define se second #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define IN(x,y) ((y).find((x))!=(y).end()) #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define DBG cerr << "debug here" << endl; #define DBGV(vari) cerr << #vari<< " = "<< (vari) < moves; void mv(int x_ball, int y_ball, int x_empty, int y_empty) { assert(x_ball >= 1 && x_ball <= n); assert(y_ball >= 1 && y_ball <= m); assert(x_empty >= 1 && x_empty <= n); assert(y_empty >= 1 && y_empty <= m); assert(abs(x_ball-x_empty) + abs(y_ball-y_empty) == 1); //cout << 1 << " " << x_ball << " " << y_ball << " " << x_empty << " " << y_empty << endl; moves.pb({x_ball, y_ball, x_empty, y_empty}); assert(s[x_ball-1][y_ball-1] == '*'); assert(s[x_empty-1][y_empty-1] == '.'); swap(s[x_ball-1][y_ball-1], s[x_empty-1][y_empty-1]); show(); } void jmp(int x_ball, int y_ball, int x_empty, int y_empty) { assert(x_ball >= 1 && x_ball <= n); assert(y_ball >= 1 && y_ball <= m); assert(x_empty >= 1 && x_empty <= n); assert(y_empty >= 1 && y_empty <= m); assert(x_ball == x_empty || y_ball == y_empty); assert(abs(x_ball-x_empty) + abs(y_ball-y_empty) == 2); //cout << 2 << " " << x_ball << " " << y_ball << " " << x_empty << " " << y_empty << endl; moves.pb({x_ball, y_ball, x_empty, y_empty}); assert(s[x_ball-1][y_ball-1] == '*'); assert(s[x_empty-1][y_empty-1] == '.'); swap(s[x_ball-1][y_ball-1], s[x_empty-1][y_empty-1]); if (x_ball == x_empty) { assert(s[x_ball-1][min(y_ball, y_empty)+1-1] == '*'); s[x_ball-1][min(y_ball, y_empty)+1-1] = '.'; } else { assert(s[min(x_ball, x_empty)+1-1][y_ball-1] == '*'); s[min(x_ball, x_empty)+1-1][y_ball-1] = '.'; } show(); } void solve_row(int x) { int y = 1; int em = 1; while (em < m-1) { mv(x, y+1, x, y); ++y; mv(x, y+1, x, y); ++y; jmp(x, y-2, x, y); --y; em++; } } void solve_col(int y) { int x = 1; int em = 1; while (em < n-1) { mv(x+1, y, x, y); ++x; mv(x+1, y, x, y); ++x; jmp(x-2, y, x, y); --x; em++; } } void solve3_row() { //cout << "solve3" << endl; int y = m-2; mv(n, y+1, n, y); ++y; mv(n, y+1, n, y); ++y; jmp(n, y-2, n, y); --y; } void solve3_col() { //cout << "solve3" << endl; int x = n-2; mv(x+1, m, x, m); ++x; mv(x+1, m, x, m); ++x; jmp(x-2, m, x, m); --x; } void assert_result() { int cnt = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (s[i][j] == '*') { ++cnt; } } } assert(cnt == 1); } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; for (int tid = 1; tid <= t; ++tid) { moves.clear(); cin >> n >> m; assert(n >= 1 && n <= 10); assert(m >= 1 && m <= 10); int x, y; int cnt = 0; for (int i = 0; i < n; ++i) { cin >> s[i]; assert(s[i].size() == m); for (int j = 0; j < m; ++j) { if (s[i][j] == '.') { x = i+1; y = j+1; ++cnt; } } } assert(cnt == 1); if (n == 1 && m == 1) { cout << -1 << endl; continue; } if (n == 1 && m == 2) { assert_result(); cout << 0 << endl; continue; } if (m == 1 && n == 2) { assert_result(); cout << 0 << endl; continue; } if (n == 2 && m == 2) { cout << -1 << endl; continue; } //move empty to upper-left corner while (x > 1) { mv(x-1, y, x, y); --x; } while (y > 1) { mv(x, y-1, x, y); --y; } if (n == 1) { solve_row(1); } else if (m == 1) { solve_col(1); } else { solve_row(1); for (int y = 1; y < m; ++y) { solve_col(y); } mv(n, 1, n-1, 1); mv(1, m, 1, m-1); //cout << "rozwiazujemy L" << endl; solve_row(n); solve_col(m); if (n >= 3) { mv(1, m-1, 1, m); for (int i = 0; i < n-3; ++i) { mv(1+i, m, 1+i+1, m); } for (int i = 0; i < m-1; ++i) { mv(n-1, 1+i, n-1, 1+i+1); } mv(n-2, m, n-2, m-1); solve3_col(); mv(n-2, m-1, n-2, m); mv(n-2, m, n-1, m); solve3_col(); } else { mv(n-1, 1, n, 1); for (int i = 0; i < m-3; ++i) { mv(n, 1+i, n, 1+i+1); } for (int i = 0; i < n-1; ++i) { mv(1+i, m-1, 1+i+1, m-1); } mv(n, m-2, n-1, m-2); solve3_row(); mv(n-1, m-2, n, m-2); mv(n, m-2, n, m-1); solve3_row(); } } assert_result(); cout << moves.size() << endl; assert(moves.size() <= 5000); for (auto& m : moves) { cout << m << endl; } } return 0; }