(C++)白駿18405競合伝染
質問と回答
https://www.acmicpc.net/problem/18405
BFS
ウイルス発生時間+ウイルス優先度の問題に基づいています.
まずウイルス構造体を定義し,次いで優先度の低いウイルス順で探索した.
コード#コード#
#include <iostream>
#include <queue>
using namespace std;
int arr[205][205]; int N;
bool check[205][205];
const int dx[4] = {0,0,1,-1};
const int dy[4] = {-1,1,0,0};
struct virus{
int cnt;
int y;
int x;
int val;
virus(int a, int b, int c, int d) : cnt(a), y(b), x(c), val(d) {};
};
struct cmp{
bool operator()(const virus &a, const virus &b){
if(a.cnt==b.cnt) return a.val>b.val;
else return a.cnt>b.cnt;
}
};
int main(){
ios_base::sync_with_stdio(0),
cin.tie(0),
cout.tie(0);
int K;
cin>>N>>K;
priority_queue<virus, vector<virus>, cmp> pq;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin>>arr[i][j];
if(arr[i][j]>0) pq.push(virus(0, i, j, arr[i][j]));
}
}
int S,X,Y;
cin>>S>>X>>Y;
while(!pq.empty()){
auto tmp = pq.top();
pq.pop();
if(tmp.cnt>=S) break;
for(int k=0; k<4; k++){
int y = tmp.y + dy[k];
int x = tmp.x + dx[k];
if(y<0 || y>=N || x<0 || x>=N) continue;
if(arr[y][x]>0) continue;
arr[y][x] = tmp.val;
pq.push({tmp.cnt+1, y, x, arr[y][x]});
}
}
/* for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cout<<arr[i][j]<<" ";
}
cout<<'\n';
}*/
cout<<arr[X-1][Y-1];
}
Reference
この問題について((C++)白駿18405競合伝染), 我々は、より多くの情報をここで見つけました https://velog.io/@minayeah/C-백준-18405-경쟁적-전염テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol