我是本题作者。 本题通过改编地图寻路而来，但是放了一些homo元素。 我们这题用广搜（深搜过不了），标准的广搜模板就ok了。

#include <bits/stdc++.h>
using namespace std;
int t;
int main(void) {
	cin >> t;
	vector<int> ans;
	while (t--) {
		int n, m;
		cin >> n >> m;
		char grid[100][100];
		for (int i = 0;i < n;++i) {
			string row;
			cin >> row;
			for (int j = 0;j < m;++j) {
				grid[i][j] = row[j];
			}
		}
		if (grid[0][0] == '*') {
			ans.push_back(1919810);
			continue;
		}
		queue<pair<int, int>> q;
		q.push({0, 0});
		grid[0][0] = '*'; 
		bool found = false;
		int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 
		
		while (!q.empty()) {
			auto [x, y] = q.front();
			q.pop();
			if (x == n - 1 && y == m - 1) {
				found = true;
				break;
			}
			for (auto& dir : dirs) {
				int nx = x + dir[0];
				int ny = y + dir[1];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.') {
					grid[nx][ny] = '*'; 
					q.push({nx, ny});
				}
			}
		}
		ans.push_back(found ? 114514 : 1919810);
	}
	
	for (size_t i = 0;i < ans.size();++i) {
		if (i > 0) {
			cout << " ";
		}
		cout << ans[i];
	}
	cout << endl;
	
	return 0;
}