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; }