病毒感染时间 题解 MarsCode

最近看到字节的豆包出了个MarsCode平台，里面有100道题目，说是可以用AI辅助，但没个正确题解，也没有全部的测试用例。试着写了两道，字节果然还是碰不起。。

第三题病毒感染时间，看着是个BFS+队列，但是有个额外的条件是一秒内被周围的两个人分别感染一次也可以感染上，所以变成了优先队列，和Dijkstra很相似。

测试用例不全也不知道写的对不对捏，给的倒是都通过了

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>using namespace std;
typedef pair<int,int> PII;struct node{int x, y;int dist;node(int dist, int x, int y):dist(dist), x(x), y(y){}bool operator<(const node& b) const{return dist > b.dist;}
};int vis[256][256];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int solution(int n, int m, std::vector<std::vector<int>> seats, std::vector<int> patient) {// 不知道为什么要有个超出边界的用例，就加上了if(patient[0] >= seats.size() || patient[1] >= seats[0].size()) return 0;// 应该使用BFS+优先级队列，更优的优先扩展priority_queue<node> pq;pq.emplace(0, patient[0], patient[1]);vector<vector<int>> time(n, vector<int>(m, 9999));time[patient[0]][patient[1]] = 0;memset(vis, 0, sizeof vis);while(!pq.empty()){auto r = pq.top(); pq.pop();if(vis[r.x][r.y]) continue;vis[r.x][r.y] = 1;for(int i = 0; i < 4; i ++){int xx = r.x + dir[i][0], yy = r.y + dir[i][1];if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;// 此时是这个位置被加入队列多次，但之前更优的被扩展过了，所以这个就忽略if(vis[xx][yy]) continue;if(time[xx][yy] == 9999){ // 未被感染，9999就是个标记，随便自己if(seats[xx][yy] == 0) {time[xx][yy] = time[r.x][r.y] + 1;} else time[xx][yy] =  time[r.x][r.y] + 2;pq.emplace(time[xx][yy], xx, yy);} else if(time[xx][yy] == time[r.x][r.y] + 2){ // 同时感染time[xx][yy] = time[r.x][r.y] + 1;// 重新加入队列，这个点可能更优pq.emplace(time[xx][yy],xx, yy);} else if(time[xx][yy] > time[r.x][r.y] + 2){// 更快被感染time[xx][yy] = time[r.x][r.y] + (seats[xx][yy] == 0 ? 1 : 2);// 重新加入队列pq.emplace(time[xx][yy],xx, yy);}}}int tick = 0;for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){tick = max(tick , time[i][j]); // 最晚的扩展时间// cout << time[i][j] << " ";}cout << endl;}return tick;
}int main() {//  You can add more test cases herestd::vector<std::vector<int>> testSeats1 = {{0,1,1,1},{1,0,1,0},{1,1,1,1},{0,0,0,1}};std::vector<std::vector<int>> testSeats2 = {{0,1,1,1},{1,0,1,0},{1,1,1,1},{0,0,0,1}};std::vector<std::vector<int>> testSeats3 = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};std::vector<std::vector<int>> testSeats4 = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};std::vector<std::vector<int>> testSeats5 = {{1}};std::cout << (solution(4, 4, testSeats1, {2, 2}) == 6) << std::endl;std::cout << (solution(4, 4, testSeats2, {2, 5}) == 0) << std::endl;std::cout << (solution(4, 4, testSeats3, {2, 2}) == 4) << std::endl;std::cout << (solution(4, 4, testSeats4, {2, 2}) == 6) << std::endl;std::cout << (solution(1, 1, testSeats5, {0, 0}) == 0) << std::endl;return 0;
}