京东笔试，算法岗第二题解答

#include<vector>
#include<iostream>
#include<string>
using namespace std;


void makeroute(vector<string>& str, int n, int m, int i, int j)
{
	if (i < 0 || i >= n || j < 0 || j >= m) return;
	if (str[i][j]!='1'&&str[i][j] != '#')
	{
		str[i][j] = '1';
		makeroute(str, n, m, i - 1, j);
		makeroute(str, n, m, i + 1, j);
		makeroute(str, n, m, i, j - 1);
		makeroute(str, n, m, i, j + 1);
	}
}

bool canbreak(vector<string>& str, int n, int m)
{
	int si, sj;
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++)
		{
			if (str[i][j] == 'S') {
				si = i;
				sj = j;
				break;
			}
		}
	}
	vector<string> ss;
	for (int t = 0;t < 3;t++) {
		for (int i = 0;i < n;i++){
			string tmp = str[i] + str[i] + str[i];
			ss.push_back(tmp);
		}
	}
	makeroute(ss, 3*n, 3*m, n+si, m+sj);
	for (int i = 0;i < 3 * n;i++)
		if (ss[i][0] == '1' || ss[i][3 * m - 1] == '1') return true;
	for (int j = 0;j < 3 * m;j++)
		if (ss[0][j] == '1' || ss[3 * n - 1][j] == '1') return true;
	return false;
}

int main()
{
	int t;
	cin >> t;
	vector<string> res;
	for (int i = 0;i < t;i++)
	{
		int n, m;
		cin >> n >> m;
		vector<string> str(n);
		for (int i = 0;i < n;i++)
			cin >> str[i];
		if (canbreak(str, n, m)) res.push_back("Yes");
		else res.push_back("No");
	}
	for (int i = 0;i < t;i++)
		cout << res[i] << endl;
	return 0;
}