商汤第一题代码

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

int main() {
	string temp;
	int n, m, start_x, start_y, get_flag = 0;
	vector<vector<int>> dir = { {0,1},{0,-1},{1,0},{-1,0} };
	while (cin >> n >> m) {
		if (n == 0 && m == 0) break;
		vector<vector<char>> mat(n, vector<char>(m, 0));
		vector<int> key(5, 0);
		int loop_flag = 1, res = 0;
		for (int i = 0; i < n; i++) {
			cin >> temp;
			for (int j = 0; j < m; j++) {
				char now = temp[j];
				mat[i][j] = now;
				if (now <= 'e' && now >= 'a') key[now - 'a']++;
				else if (now == 'S') {
					start_x = i;
					start_y = j;
					mat[i][j] = '.';
				}
			}
		}
		//bfs
		while (loop_flag) {
			loop_flag = 0;
			vector<vector<char>> visited(n, vector<char>(m, 0));
			queue<int> qx, qy;
			qx.push(start_x);
			qy.push(start_y);
			visited[start_x][start_y] = 1;
			while (!qx.empty()) {
				int cur_x = qx.front();
				int cur_y = qy.front();
				char now = mat[cur_x][cur_y];
				qx.pop();
				qy.pop();
				if (now == 'G') {
					get_flag = 1;
					break;
				}
				if (now >= 'A' && now <= 'E' && key[now - 'A'] != 0) continue;
				if (now <= 'e' && now >= 'a') {
					mat[cur_x][cur_y] = '.';
					key[now - 'a']--;
					if (key[now - 'a'] == 0) loop_flag = 1;
				}
				for (auto xy : dir) {
					int nx = cur_x + xy[0];
					int ny = cur_y + xy[1];
					if (nx >= 0 && nx < n && ny >= 0 && ny < m && mat[nx][ny] != 'X' && visited[nx][ny] != 1) {
						visited[nx][ny] = 1;
						qx.push(nx);
						qy.push(ny);
					}
				}
			}
		}
		loop_flag = 1;
		if (get_flag) {
			cout << "YES" << endl;
			get_flag = 0;
		}
		else cout << "NO" << endl;
	}

}