商汤第一题代码
第一题就是几遍bfs，若走一遍没发现有key被置为0，则退出bfs
第二题的数学操作是知识盲区，第一题A了后就交卷了。
#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;
}
} #笔试题目#
