紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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