結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-25 01:16:43 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 664 ms / 3,000 ms |
コード長 | 1,810 bytes |
コンパイル時間 | 726 ms |
コンパイル使用メモリ | 90,620 KB |
実行使用メモリ | 113,360 KB |
最終ジャッジ日時 | 2024-11-06 16:05:08 |
合計ジャッジ時間 | 4,199 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
/* -*- coding: utf-8 -*-** 402.cc: No.402 最も海から遠い場所 - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_H = 3000;const int MAX_W = 3000;const int INF = 1 << 30;const int dxs[] = {1, 1, 0, -1, -1, -1, 0, 1};const int dys[] = {0, -1, -1, -1, 0, 1, 1, 1};/* typedef */typedef pair<int,int> pii;/* global variables */int dists[MAX_H][MAX_W];/* subroutines *//* main */int main() {int h, w;cin >> h >> w;int maxd = 0;queue<pii> q;for (int y = 0; y < h; y++) {string s;cin >> s;for (int x = 0; x < w; x++) {if (s[x] == '.')dists[y][x] = 0, q.push(pii(x, y));elsedists[y][x] = -1;}}for (int y = 0; y < h; y++) {if (dists[y][0] < 0)dists[y][0] = 1, q.push(pii(0, y)), maxd = 1;if (dists[y][w - 1] < 0)dists[y][w - 1] = 1, q.push(pii(w - 1, y)), maxd = 1;}for (int x = 0; x < w; x++) {if (dists[0][x] < 0)dists[0][x] = 1, q.push(pii(x, 0)), maxd = 1;if (dists[h - 1][x] < 0)dists[h - 1][x] = 1, q.push(pii(x, h - 1)), maxd = 1;}while (! q.empty()) {pii u = q.front(); q.pop();int &ux = u.first, &uy = u.second;int vd = dists[uy][ux] + 1;for (int di = 0; di < 8; di++) {int vx = ux + dxs[di], vy = uy + dys[di];if (vx >= 0 && vx < w && vy >= 0 && vy < h && dists[vy][vx] < 0) {dists[vy][vx] = vd;q.push(pii(vx, vy));maxd = vd;}}}printf("%d\n", maxd);return 0;}