面白かった。BFS したり、Warshall--Floyd したり。

問題概要

$H \times W$ の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。

「通路を 2 箇所 $s, t$ 指定したときの、上下左右に通路のみをたどって $s$ から $t$ へたどりつくのに必要な最小回数」

の最大値を求めよ。

制約

$1 \le H, W \le 20$

解法 1：全マスを始点とした BFS

BFS についてはここに書いた

qiita.com

すべてのマスに対して「そのマスを始点とした各マスへの最短路超」を求める。

$O(HW)$ 回だけ BFS をやるので、計算量は $O(H^{2}W^{2})$ になる。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// (x, y) を始点とした BFS をして、(x, y) から最も遠いマスへの距離を答える
int bfs(const vector<string> &v, int x, int y) {
    int H = v.size(), W = v[0].size();
    vector<vector<int>> dist(H, vector<int>(W, -1));
    queue<pair<int,int>> que;

    int res = 0;
    que.push({x, y});
    dist[x][y] = 0;
    while (!que.empty()) {
        int x = que.front().first, y = que.front().second;
        res = max(res, dist[x][y]);
        que.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x+ dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (v[nx][ny] == '#') continue;
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                que.push({nx, ny});
            }
        }
    }
    return res;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> v(H);
    for (int i = 0; i < H; ++i) cin >> v[i];

    int res = 0;
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            if (v[x][y] == '#') continue;
            res = max(res, bfs(v, x, y));
        }
    }
    cout << res << endl;
}

解法 2： Warshall--Floyd 法

通路を「頂点」、隣接する通路を「辺」とみたグラフにおいて、全頂点間の最短距離を求めて、その最大値を求めれば OK。

全頂点間の最短路は、Floyd--Warshall 法などによって、以下のようなとても簡単な実装で求めることができる。頂点数が $O(HW)$ 個なので、計算量は $O(H^{3}W^{3})$ 。

// dp[ x ][ y ] を辺 (x, y) の長さに初期化しておく、辺がないところは INF
for (int k = 0; k < V; ++k)
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            chmin(dp[i][j], dp[i][k] + dp[k][j]);

なお実装では、「#」のマスも「孤立した頂点」としてみなした方が実装しやすい。また、マス (i, j) の頂点番号を i × W + j とした。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 500;
const int INF = 1<<29;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int dp[MAX][MAX];

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    for (int i = 0; i < H; ++i) cin >> s[i];
    auto id = [&](int x, int y) { return x * W + y; };

    // 初期化
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) dp[i][j] = INF;
        dp[i][i] = 0; // これを忘れないように
    }

    // make graph
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            if (s[x][y] == '#') continue;
            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir], ny = y + dy[dir];
                if (nx < 0 || nx >= H || ny < 0 || ny >= W || s[nx][ny] == '#')
                    continue;
                dp[id(x, y)][id(nx, ny)] = 1;
                dp[id(nx, ny)][id(x, y)] = 1;
            }
        }
    }

    // Floyd--Warshall
    int V = H*W;
    for (int k = 0; k < V; ++k)
        for (int i = 0; i < V; ++i)
            for (int j = 0; j < V; ++j)
                chmin(dp[i][j], dp[i][k] + dp[k][j]);

    int res = 0;
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            if (s[x][y] == '#') continue;
            for (int x2 = 0; x2 < H; ++x2) {
                for (int y2 = 0; y2 < W; ++y2) {
                    if (s[x2][y2] == '#') continue;                 
                    chmax(res, dp[id(x, y)][id(x2, y2)]);
                }
            }
        }
    }
    cout << res << endl;
}