정올 3231 / 백준 15972 물탱크

algorithm :  proiority_queue, BFS

 

해설

 

각 모서리 부분을 queue에 넣은 다음  BFS를 돌리면서 최악에 경우 제일 많이 빠지는 경우만 water변수에 저장

water 의 합을 출력

#include<bits/stdc++.h>
#define LM 1000+10
#define INF 199999999
using LL = long long;
using namespace std;
 
int N,M,H;
int A[LM][LM];
int B[LM][LM];
int visit[LM][LM];
int water[LM][LM];
int ans;
 
struct data{
    int x,y,high,mx;
    bool operator<(const data &r)const{
        return r.high < high;
    }
};
priority_queue<data> pq;
void input(){
    scanf("%d %d %d",&N,&M,&H);
    for(int i = 1 ; i <= N + 1 ; i ++){
        for(int j = 1 ; j <= M ; j ++)
            scanf("%d",&A[i][j]);
    }
    for(int i = 1 ; i <= N; i ++){
        for(int j = 1 ; j <= M + 1 ; j ++)
            scanf("%d",&B[i][j]);
    }
}
 
void Push(int x,int y,int high,int mx){
    if(high == -1 || x < 1 || M < x || y < 1 || N < y ||visit[y][x])return;
    pq.push({x,y,high,max(mx,high)});
}
 
void BFS(){
    while(!pq.empty()){
        auto t = pq.top();
        pq.pop();
        if(visit[t.y][t.x])continue;
        water[t.y][t.x] = max(t.mx,t.high);
        visit[t.y][t.x] = 1;
        Push(t.x,t.y - 1,A[t.y][t.x],t.mx);
        Push(t.x + 1,t.y,B[t.y][t.x + 1],t.mx);
        Push(t.x,t.y + 1,A[t.y + 1][t.x],t.mx);
        Push(t.x - 1,t.y,B[t.y][t.x],t.mx);
    }
 
}
 
int main(){
    //freopen("input.txt","r",stdin);
    input();
    for(int i = 1 ; i <= M ; i++)
        Push(i,1,A[1][i],0);
    for(int i = 1 ; i <= M ; i++)
        Push(i,N,A[N + 1][i],0);
    for(int i = 1 ; i <= N ; i++)
        Push(1,i,B[i][1],0);
    for(int i = 1 ; i <= N ; i++)
        Push(M,i,B[i][M + 1],0);
    BFS();
     for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= M ; j++){
            if(!visit[i][j]) ans += H;
            else ans += water[i][j];
        }
    }
    printf("%d",ans);
    return 0;
}