C - 壁抜け / AtCoderBeginnerContest#020

abc020.contest.atcoder.jp

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

幅優先探索+二分探索で最大値を求め、出力。
〜了〜