并非玄米 level
获赞
21
粉丝
12
关注
3
看过 TA
327
重庆邮电大学
2024
C++
IP属地:江苏
暂未填写个人简介
私信
关注
2024-09-06 12:42
已编辑
重庆邮电大学 C++
#include<iostream>#include<vector>#include<string>#include<queue>#include<climits>using namespace std;vector<vector<int>> checknum = { {1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,-1},{-2,1} };void bfs(vector<vector<int>>& board, vector<vector<int>>& numofhourse, vector<vector<int>>& stepnum,int n,int m){int maxstep = board[n][m];int step = 0;queue<pair<int, int>> que;que.push({ n,m });vector<vector<bool>> checkboard(board.size(), vector<bool>(board[0].size(), 0));while (!que.empty() && step < maxstep) {int size = que.size();for (int i = 0; i < size; i++) {int x = que.front().first;int y = que.front().second;que.pop();stepnum[x][y] += step;numofhourse[x][y]++;checkboard[x][y] = 1;for (int j = 0; j < checknum.size(); j++) {int nx = x + checknum[j][0];int ny = y + checknum[j][1];if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && checkboard[nx][ny] == 0) {checkboard[nx][ny] = 1;que.push({ nx,ny });}}}step++;}}int main() {int row, col;cin >> row >> col;vector<vector<int>> board(row, vector<int>(col, 0));vector<vector<int>> numofhourse = board;vector<vector<int>> stepnum(row, vector<int>(col, 0));int counthourse = 0;for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {string temp;cin >> temp;if (temp != ".") {board[i][j] = stoi(temp);counthourse++;}}}for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (board[i][j] > 0) {bfs(board, numofhourse, stepnum, i, j);}}}int minstep = INT_MAX;for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (numofhourse[i][j] == counthourse) {if (stepnum[i][j] < minstep) {minstep = stepnum[i][j];}}}}if (minstep == INT_MAX) {cout << "0";}else {cout << minstep;}return 0;}
0 点赞 评论 收藏
分享
2024-08-23 06:02
已编辑
重庆邮电大学 C++
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务