結果

問題 No.402 最も海から遠い場所
ユーザー kohei2019kohei2019
提出日時 2023-08-14 15:52:00
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 726 ms / 3,000 ms
コード長 1,361 bytes
コンパイル時間 4,884 ms
コンパイル使用メモリ 91,304 KB
実行使用メモリ 129,848 KB
最終ジャッジ日時 2023-08-14 15:52:12
合計ジャッジ時間 9,150 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,384 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 4 ms
4,380 KB
testcase_14 AC 3 ms
4,380 KB
testcase_15 AC 15 ms
5,936 KB
testcase_16 AC 20 ms
6,804 KB
testcase_17 AC 260 ms
46,856 KB
testcase_18 AC 726 ms
60,420 KB
testcase_19 AC 449 ms
129,848 KB
testcase_20 AC 490 ms
56,652 KB
testcase_21 AC 416 ms
93,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> lsHW(H + 2, string(W + 2, '.'));
    for (int i = 1; i <= H; ++i) {
        string row;
        cin >> row;
        lsHW[i] = '.' + row + '.';
    }
    H += 2;
    W += 2;
    const int INF = 5000;
    vector<vector<int>> cost(H, vector<int>(W, INF));
    vector<pair<int, int>> dxy = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
    deque<pair<int, int>> d;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (lsHW[i][j] == '.') {
                cost[i][j] = 0;
                d.emplace_back(i, j);
            }
        }
    }
    int cmax = 0;
    while (!d.empty()) {
        int x = d.front().first;
        int y = d.front().second;
        d.pop_front();
        for (const auto& dxdy : dxy) {
            int dx = dxdy.first;
            int dy = dxdy.second;
            if (0 <= x + dx && x + dx < H && 0 <= y + dy && y + dy < W) {
                if (cost[x + dx][y + dy] > cost[x][y] + 1) {
                    cost[x + dx][y + dy] = cost[x][y] + 1;
                    cmax = cost[x][y] + 1;
                    d.emplace_back(x + dx, y + dy);
                }
            }
        }
    }
    cout << cmax << endl;
    return 0;
}
0