結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-22 23:55:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,640 ms / 3,000 ms |
コード長 | 1,598 bytes |
コンパイル時間 | 1,973 ms |
コンパイル使用メモリ | 175,328 KB |
実行使用メモリ | 225,376 KB |
最終ジャッジ日時 | 2024-11-06 13:30:46 |
合計ジャッジ時間 | 10,079 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)typedef long long ll;int H, W;string S[3010];//-----------------------------------------------------------------struct Comp {bool operator() (pair<int,ll> a, pair<int,ll> b) {return a.second > b.second;}};#define INF INT_MAX/2int dx[8] = { 0,1,1,1,0,-1,-1,-1 };int dy[8] = { -1,-1,0,1,1,1,0,-1 };bool done[3010][3010];ll dist[3010][3010];ll solve() {priority_queue<pair<int, ll>, vector<pair<int, ll> >, Comp> que;rep(y, 0, H) rep(x, 0, W) dist[y][x] = INF;rep(y, 0, H) rep(x, 0, W) {if ((x != 0 && x != W - 1) && (y != 0 && y != H - 1)) continue;if (S[y][x] == '#') {dist[y][x] = 1;done[y][x] = true;que.push(make_pair(y * 10000 + x, 1));}else {dist[y][x] = 0;done[y][x] = true;que.push(make_pair(y * 10000 + x, 0));}}while (!que.empty()) {auto q = que.top(); que.pop();int x = q.first % 10000;int y = q.first / 10000;ll c = q.second;rep(i, 0, 8) {int yy = y + dy[i];int xx = x + dx[i];if (yy < 0 || H <= yy) continue;if (xx < 0 || W <= xx) continue;if (done[yy][xx]) continue;int cc = c + 1;if (S[yy][xx] == '.') cc = 0;if (cc < dist[yy][xx]) {dist[yy][xx] = cc;done[yy][xx] = true;que.push(make_pair(yy * 10000 + xx, cc));}}}ll ans = 0;rep(y, 0, H) rep(x, 0, W) ans = max(ans, dist[y][x]);return ans;}//-----------------------------------------------------------------int main(){cin >> H >> W;rep(y, 0, H) cin >> S[y];cout << solve() << endl;}