网易云 4月17号 笔试题第三题

# include<iostream>
# include<string>
# include<vector>

using namespace std;

const int dist[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

void bankstrack(vector<string> & mys, int & mk, int i, int j, int step, int& result, int st, vector <vector<int>> &visited) {
	if (st == 0 && mys[i][j] != 'M') {
		step++;

	}
	if (mys[i][j] == 'E') {
		if (st != 0) {
			step++;
		}

		result = min(result, step);
		return;
	}
	if (st == 0 && mys[i][j] == 'M') {
		return;
	}
	if (st != 0) {

		for (int t = 0; t < 4; t++) {
			int dx = i + dist[t][0];
			int dy = j + dist[t][1];

			if (dx >= 0 && dx < mys.size() && dy >= 0 && dy < mys[0].size() && mys[dx][dy] != 'S' && mys[dx][dy] != 'W' && visited[dx][dy] == 0) {
	
				st--;
				visited[dx][dy] = 1;
				bankstrack(mys, mk, dx, dy, step, result, st, visited);
				visited[dx][dy] = 0;
				st++;
			}
		}
	}
	else if(st == 0)
		for (int k = 0; k < mk; k++) {
			for (int t = 0; t < 4; t++) {
				int dx = i + dist[t][0];
				int dy = j + dist[t][1];
				if (dx >= 0 && dx < mys.size() && dy >= 0 && dy < mys[0].size() && mys[dx][dy] != 'S' && mys[dx][dy] != 'W' && visited[dx][dy] == 0) {
					visited[dx][dy] = 1;
					bankstrack(mys, mk, dx, dy, step, result, k, visited);
					visited[dx][dy] = 0;
				}
			}
		}
}

int main() {

	int T;
	cin >> T;
	vector<int> result;
	vector<vector<string>> mys;
	vector<vector<int>> nums;
	while (T--) {
		int N, M, K;
		cin >> M >> N >> K;
		nums.push_back({N, M, K});
		vector<string> str;
		while (M--) {
			string t;
			cin >> t;
			str.push_back(t);
		}
		mys.push_back(str);
	}
	for (int i = 0; i < mys.size(); i++) {
		int mk = nums[i][2];
		int t = INT32_MAX;
		int step = 0;
		vector <vector<int>> visited(nums[i][1], vector<int>(nums[i][0] , 0));
		for (int j = 0; j < mys[i].size(); j++) {
			for (int k = 0; k < mys[i][0].size(); k++) {
				if (mys[i][j][k] == 'S') {
					for (int e = 1; e <= mk; e++) {
						visited[j][k] = 1;
						bankstrack(mys[i], mk, j, k, step, t, e, visited);
					}
					break;
				}
			}
		}
		if (t == INT32_MAX) {
			result.push_back(-1);
		}
		else result.push_back(t);
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << endl;
	}
	system("pause");
	return 0;

}