若图中存在点使得删去它后 \(S, T\) 不连通，那么 A 可以一步获胜。
否则，双方都不会删去一个点使得删去它后会产生一个点使得删去它后 \(S, T\) 不连通。那么到最后图上会剩下两条 \(S \to T\) 的不交路径。此时一方无论如何操作都会使得另一方获胜。
因为这是二分图，所以这两条路径的并的点数一定为偶数。那么只用判断初始时非障碍格数量的奇偶性，就能知道到达终态步数的奇偶性。
时间复杂度 \(O(\sum nm)\)。
注意不能直接套割点的板子。
code
// Problem: L - Maze Game
// Contest: AtCoder - UTPC 2021
// URL: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_l
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define ID(x, y) (((x) - 1) * m + (y))
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 110;
const int maxm = 10050;
int n, m, dep[maxm], low[maxm], fa[maxm];
char s[maxn][maxn];
vector<int> G[maxm];
void dfs(int u) {
low[u] = dep[u];
for (int v : G[u]) {
if (!dep[v]) {
fa[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dep[v]);
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n * m; ++i) {
vector<int>().swap(G[i]);
dep[i] = low[i] = fa[i] = 0;
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= m; ++j) {
cnt += (s[i][j] != '#');
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i < n && s[i][j] != '#' && s[i + 1][j] != '#') {
G[ID(i, j)].pb(ID(i + 1, j));
G[ID(i + 1, j)].pb(ID(i, j));
}
if (j < m && s[i][j] != '#' && s[i][j + 1] != '#') {
G[ID(i, j)].pb(ID(i, j + 1));
G[ID(i, j + 1)].pb(ID(i, j));
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s[i][j] == 'S') {
dep[ID(i, j)] = 1;
dfs(ID(i, j));
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s[i][j] == 'G') {
int u = ID(i, j);
while (fa[fa[u]]) {
if (low[u] >= dep[u] - 1) {
puts("Alice");
return;
}
u = fa[u];
}
}
}
}
puts((cnt & 1) ? "Alice" : "Bob");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}