結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-23 00:29:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 601 ms / 3,000 ms |
コード長 | 1,872 bytes |
コンパイル時間 | 771 ms |
コンパイル使用メモリ | 65,756 KB |
実行使用メモリ | 159,220 KB |
最終ジャッジ日時 | 2024-11-06 10:06:27 |
合計ジャッジ時間 | 4,011 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream>#include <queue>using namespace std;struct State {int row, col, dist;State(int row, int col, int dist) : row(row), col(col), dist(dist) { }};const int kINF = 1 << 28;const int kMAX_H = 3100;const int kMAX_W = 3100;string S[kMAX_H];int dist[kMAX_H][kMAX_W];int H, W;bool IsIn(int row, int col) {return 0 <= row && row < H && 0 <= col && col < W;}int main() {cin.tie(0);ios::sync_with_stdio(false);cin >> H >> W;for (int r = 0; r < H; r++) {cin >> S[r];}queue<State> que;fill((int* )dist, (int* )(dist + kMAX_H), kINF);for (int r = 0; r < H; r++) {for (int c = 0; c < W; c++) {if (S[r][c] == '.') {que.push(State(r, c, 0));dist[r][c] = 0;}}}while (!que.empty()) {State s = que.front(); que.pop();for (int dr = -1; dr <= 1; dr++) {for (int dc = -1; dc <= 1; dc++) {int nr = s.row + dr, nc = s.col + dc;if (IsIn(nr, nc) && S[nr][nc] == '#' && dist[nr][nc] == kINF) {que.push(State(nr, nc, s.dist + 1));dist[nr][nc] = s.dist + 1;}}}}int ans = 0;for (int r = 0; r < H; r++) {for (int c = 0; c < W; c++) {if (S[r][c] == '.') continue;/*if (S[r][c] == '.') {cout << "x ";continue;}*/int move_r = min(r, H - 1 - r) + 1,move_c = min(c, W - 1 - c) + 1,c_dist = min(move_r, move_c);ans = max(ans, min(dist[r][c], c_dist));// cout << min(dist[r][c], c_dist) << " ";}// cout << endl;}cout << ans << endl;return 0;}