백준 25902 - Rising Tides

문제링크 : https://www.acmicpc.net/problem/25902

파라메트릭서치 기본문제이다.

동굴의 높이(mid)를 기준으로
int s,e로 이분탐색해주면서
최소의 최대값을 찾아주면된다.

시간복잡도는 O(log(ai)*r*c) 이 된다.

if(m>v[0][0]) return false;
나
ans==0||ans==-1

같은 엣지 케이스들에 대해서 주의하자..

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int r,c;
vector<int> v[500];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void clear(){
    for(int i=0;i<500;i++) v[i].clear();
}
bool visited[500][500];
bool sol(int m){
    if(m>v[0][0]) return false;
    queue<pair<int,pair<int,int>>> q;
    memset(visited,false,sizeof(visited));
    visited[0][0]=true;
    q.push({0,{0,0}});
    while(!q.empty()){
        int x = q.front().second.first;
        int y = q.front().second.second;
        int cost = q.front().first;
        q.pop();
        if(x==c-1&&y==r-1) return true;
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0>nx||nx>=c||0>ny||ny>=r) continue;
            int h = v[ny][nx];
            if(m<=h-(cost+1)){
                if(!visited[ny][nx]){
                    visited[ny][nx]=true;
                    q.push({cost+1,{nx,ny}});
                }
            }
        }
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T){
        T--;
        clear();
        cin>>r>>c;
        for(int i=0;i<r;i++){
            for(int t=0;t<c;t++){
                int a;cin>>a;
                v[i].push_back(a);
            }
        }
        int ans = -1;
        int s = 0; int e = 1e9;
        while(s<=e){
            int mid = (s+e)/2;
            if(sol(mid)){
                ans = mid;
                s = mid+1;
            }else{
                e = mid-1;
            }
        }
        if(ans==0||ans==-1) cout<<"impossible"<<"\n";
        else cout<<ans<<"\n";
    }
}