結果

問題 No.157 2つの空洞
コンテスト
ユーザー kichirb3
提出日時 2018-03-10 11:44:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,513 bytes
コンパイル時間 979 ms
コンパイル使用メモリ 94,040 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 05:04:10
合計ジャッジ時間 1,721 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int solve(std::vector<std::vector<char> >&, unsigned int, unsigned int)':
main.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^
main.cpp:61:48: warning: 'start_node' may be used uninitialized [-Wmaybe-uninitialized]
   61 |     vector<int> dist = dijkstra(adj, start_node);
      |                                                ^
main.cpp:48:9: note: 'start_node' was declared here
   48 |     int start_node;
      |         ^~~~~~~~~~

ソースコード

diff # 

// No.157 2つの空洞
// https://yukicoder.me/problems/no/157
//

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


// グラフ問題用。
struct edge {
    int to;
    int cost;
};
typedef pair<int, int> P;       // 最短距離と頂点の番号
const int INF = 999999999;      // エッジが無いことを示す数字

vector<int> dijkstra(vector<vector<edge>>& adj, int s);
int solve(vector<vector<char>> &maze, unsigned int W, unsigned int H);
vector<vector<edge>> prepare_graph(vector<vector<char>> &maze, unsigned int W, unsigned int H);


int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    unsigned int W, H;
    cin >> W >> H;
    vector<vector<char>> maze(H);
    for (auto y = 0; y < H; ++y) {
        maze[y].resize(W);
        for (auto x = 0; x < W; ++x)
            cin >> maze[y][x];
    }

    int ans = solve(maze, W, H);
    cout << ans << endl;
}

int solve(vector<vector<char>> &maze, unsigned int W, unsigned int H) {
    vector<vector<edge>> adj = prepare_graph(maze, W, H);

    bool found = false;
    int start_node;
    for (auto y = 1; y < H-1; y++) {
        if (found)
            break;
        for (auto x = 1; x < W - 1; ++x) {
            if (maze[y][x] == '.') {
                found = true;
                start_node = W * y + x;
                break;
            }
        }
    }

    vector<int> dist = dijkstra(adj, start_node);

    for (auto y = 1; y < H-1; ++y){
        for (auto x = 1; x < W-1; ++x) {
            int ans = dist[W*y + x];
            if (ans != 0 && maze[y][x] != '#')
                return ans;
        }
    }
}

vector<vector<edge>> prepare_graph(vector<vector<char>> &maze, unsigned int W, unsigned int H) {
    vector<vector<edge>> adj(W * H);
    vector<int> dx = {0, 0, -1, 1};
    vector<int> dy = {-1, 1, 0, 0};

    for (auto y = 1; y < H-1; ++y) {
        for (auto x = 1; x < W-1; ++x) {
            for (auto i = 0; i < dx.size(); ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (0 < nx && nx < W-1 && 0 < ny && ny < H-1) {
                    int from_node = W * y + x;
                    int to_node = W * ny + nx;
                    int cost = 1;
                    if (maze[ny][nx] == '.')
                        cost = 0;
                    adj[from_node].push_back({to_node, cost});
                }

            }
        }
    }
    return adj;
}


vector<int> dijkstra(vector<vector<edge>>& adj, int s)
{
    // 隣接リスト(各ノードごとのedgeのベクトル)を使用して、ノードsからの最短距離を計算する
    vector<int> d(adj.size()+1);    // 各ノードまでの距離距離
    fill(d.begin(), d.end(), INF ); // デフォルトではINFで埋めておく
    priority_queue<P, vector<P>, greater<P>> que; // firstが小さい順に取り出せるようにした優先度キュー
    d[s] = 0;                   //  自分への距離は0
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first)
            continue;
        for (int i = 0; i < adj[v].size(); ++i) {
            edge e = adj[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    return d;                   // 最終的な距離情報
}
0