ABC020_C

2分探索と単一始点最短経路問題の問題
dijkstra法は二次元配列と頂点の番号を対応させて考えればよい.

#include <bits/stdc++.h>
using namespace std;
/*
    考え方
    1.2文探索でtmp<=tを満たす最大のtmpを見つける
    2.dijkstra法で'#'の移動コストがtmpであるとして'S'->'G'への移動コストの最小値を求める
*/
#define ll long long int 
static const int WHITE = 1;
static const int GRAY  = 2;
static const int BLACK = 3;
static const int MAX_H = 10;
static const int MAX_W = 10;
static const ll MAX_T = 1e9;
static const ll INF   = INT_MAX;
char maze[MAX_H][MAX_W+1];
ll h,w,t;
ll dt[MAX_H][MAX_W];//頂点の始点からの最小距離
ll color[MAX_H][MAX_W];//
ll sx,sy,gx,gy;
ll dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

void dijkstra(ll tmp)
{
    //次のマスが黒色'#'だったときの移動コストをtmpとしたときのdijkstra法を用いる

    ll mincost;
    //初期化
    for(ll y=0;y<h;y++){
        for(ll x=0;x<w;x++){
            color[y][x] = WHITE;
            dt[y][x] = INF;
        }
    }
    color[sy][sx] = GRAY;
    dt[sy][sx]=0;    

    while(true){
        mincost=INF;
        ll uy=-1;
        ll ux=-1;
        for(ll y=0;y<h;y++){
            for(ll x=0;x<w;x++){
                if(color[y][x]!=BLACK && dt[y][x]<mincost){
                    mincost = dt[y][x];
                    uy=y;ux=x;  
                }
            }
        }
        if(ux==-1 || uy==-1){
            break;
        }
        color[uy][ux]=BLACK;
        for(ll i=0;i<4;i++){
            ll vy = uy+dy[i],vx=ux+dx[i];
            if(0<=vy && vy<h && 0<=vx && vx<w){
                if(color[vy][vx]!=BLACK){
                    ll cost=0;
                    if(maze[vy][vx]=='#')cost+=tmp;
                    else cost+=1;
                    if(dt[vy][vx]>dt[uy][ux]+cost){
                        dt[vy][vx]=dt[uy][ux]+cost;
                        color[vy][vx]=GRAY;
                    }
                }
            }
        }   
    }
}


bool judge(ll tmp)
{
    //tmp<=tであるかを判定
    //次のマスが黒色'#'だったときの移動コストをtmpとしたときのdijkstra法を用いる
    dt[sy][sx] = 0;
    dijkstra(tmp);
    if(dt[gy][gx]<=t)return true;
    else return false;
}

int binarySearch(ll left,ll right)
{
    //二分探索
    if(left+1==right)return left;
    ll mid = (left+right)/2;
    if(judge(mid)){
        return binarySearch(mid,right);
    }else{
        return binarySearch(left,mid);
    }
}

int main(){
    /*
        ios_base::sync_with_stdio(0); cin.tie(0);
        #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        #endif
    */

    //input
    cin>>h>>w>>t;
    for(int y=0;y<h;y++){
        scanf("%s",maze[y]);//cin>>maze[y];
    }
    //スタート地点とゴール地点を記録
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            if(maze[y][x]=='S'){
                sx=x;sy=y;
            }
            if(maze[y][x]=='G'){
                gx=x;gy=y;
            }
        }
    }
    int ans = binarySearch(0,MAX_T);
    cout<<ans<<endl;
    return 0;
}

umashika5555.hatenablog.com