結果

問題 No.402 最も海から遠い場所
ユーザー tkmst201
提出日時 2017-05-21 11:08:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2,078 ms / 3,000 ms
コード長 1,599 bytes
コンパイル時間 1,430 ms
コンパイル使用メモリ 167,148 KB
実行使用メモリ 246,568 KB
最終ジャッジ日時 2024-09-19 08:04:49
合計ジャッジ時間 10,476 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-10;
int h, w;
string maps[3000];
int d[3000][3000];
int main() {
    cin >> h >> w;
    REP(i, h) cin >> maps[i];
    
    fill(d[0], d[h], INF);
    
    priority_queue<P, vector<P>, greater<P> > pq;
    
    REP(i, h) {
        pq.push( P(1, pii(i, 0)) );
        pq.push( P(1, pii(i, w - 1)) );
        
        chmin(d[i][0], 1);
        chmin(d[i][w - 1], 1);
    }
    REP(j, w) {
        pq.push( P(1, pii(0, j)) );
        pq.push( P(1, pii(h - 1, j)) );
        
        chmin(d[0][j], 1);
        chmin(d[h - 1][j], 1);
    }
    REP(i, h) REP(j, w) if (maps[i][j] == '.') {
        pq.push( P(0, pii(i, j)) );
        chmin(d[i][j], 0);
    }
    
    while (!pq.empty()) {
        P now = pq.top(); pq.pop();
        
        int nd = now.fi;
        int x = now.se.se;
        int y = now.se.fi;
        
        FOR(dy, -1, 2) FOR(dx, -1, 2) {
            int nx = x + dx;
            int ny = y + dy;
            if (!(nx >= 0 && nx < w && ny >= 0 && ny < h)) continue;
            
            if (!chmin(d[ny][nx], nd + 1)) continue;
            pq.push( P(nd + 1, pii(ny, nx)) );
        }
    }
    
    int ans = 0;
    REP(i, h) REP(j, w) chmax(ans, d[i][j]);
    cout << ans << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0