(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];



}