C - 壁抜け / AtCoderBeginnerContest#020
#include <iostream> #include <queue> #include <string> using namespace std; #define INF (1LL<<60) typedef pair<int,int> P_II; int h, w, t; string str[10]; P_II start, goal; bool BFS(int middle) { queue<P_II> que; long long cost[10][10]; const int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1}; for (int i=0; i<h; ++i) for (int j=0; j<w; ++j) cost[i][j]=INF; que.push(start); cost[start.first][start.second]=0; while ( !que.empty() ) { P_II p_ii=que.front(); que.pop(); if (p_ii.first==goal.first && p_ii.second==goal.second && cost[goal.first][goal.second]<=t) return true; for (int d=0; d<4; ++d) if (0<=p_ii.first+dy[d] && p_ii.first+dy[d]<h && 0<=p_ii.second+dx[d] && p_ii.second+dx[d]<w) { if (str[ p_ii.first+dy[d] ][ p_ii.second+dx[d] ] == '.') { if (cost[p_ii.first][p_ii.second]+1 < cost[ p_ii.first+dy[d] ][ p_ii.second+dx[d] ]) { cost[ p_ii.first+dy[d] ][ p_ii.second+dx[d] ]=cost[p_ii.first][p_ii.second]+1; que.push( P_II(p_ii.first+dy[d],p_ii.second+dx[d]) ); } } else if (str[ p_ii.first+dy[d] ][ p_ii.second+dx[d] ] == '#') { if (cost[p_ii.first][p_ii.second]+middle < cost[ p_ii.first+dy[d] ][ p_ii.second+dx[d] ]) { cost[ p_ii.first+dy[d] ][ p_ii.second+dx[d] ]=cost[p_ii.first][p_ii.second]+middle; que.push( P_II(p_ii.first+dy[d],p_ii.second+dx[d]) ); } } } } return false; } void Solve(void) { for (int i=0; i<h; ++i) { cin >> str[i]; for (int j=0; j<w; ++j) { if (str[i][j] == 'S') { str[i][j]='.'; start=make_pair(i,j); } else if (str[i][j] == 'G') { str[i][j]='.'; goal=make_pair(i,j); } } } int low=1, high=t; while (high-low > 1) { int middle=(high+low)/2; if ( BFS(middle) ) low=middle; else high=middle; } cout << low << endl; } int main(void) { cin >> h >> w >> t; Solve(); return 0; }
幅優先探索+二分探索で最大値を求め、出力。
〜了〜