結果

問題 No.402 最も海から遠い場所
コンテスト
ユーザー paruki
提出日時 2016-07-22 23:15:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,374 bytes
コンパイル時間 1,981 ms
コンパイル使用メモリ 182,224 KB
実行使用メモリ 26,476 KB
最終ジャッジ日時 2024-11-06 13:08:56
合計ジャッジ時間 7,812 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

const int dy[] = { 0, 1, -1, 0, 1, 1, -1, -1 };
const int dx[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

int H, W;
char S[3010][3010];

int main(){
    while(cin >> H >> W){
        
        MEM(S, '.');
        rep(y, H){
            scanf("%s", S[y + 1] + 1);
            S[y + 1][W + 1] = '.';
        }
        H += 2;
        W += 2;

        vector<vi> res(H, vi(W, INT_MAX));

        priority_queue<tuple<int, int, int>> Q;
        rep(y, H)rep(x, W)if(S[y][x] == '.')Q.push(make_tuple(0, y, x));
        while(sz(Q)){
            int d, y, x;
            tie(d, y, x) = Q.top();
            Q.pop();

            if(res[y][x] != INT_MAX)continue;
            res[y][x] = -d;

            rep(i, 8){
                int ny = y + dy[i], nx = x + dx[i];
                if(ny >= 0 && nx >= 0 && ny < H && nx < W && res[ny][nx] == INT_MAX)
                    Q.push(make_tuple(d - 1, ny, nx));
            }
        }

        int ans = 0;
        rep(y, H)rep(x, W){
            smax(ans, res[y][x]);
        }

        //rep(y, H){
        //    rep(x, W)cout << res[y][x];
        //    cout << endl;
        //}
        cout << ans << endl;

        //rep(y, H){
        //    int mi = 0, ma = W - 1;
        //    rep(x, W){
        //        if(S[y][x] == '.')mi = x;
        //        smin(res[y][x], x - mi);
        //    }
        //    for(int x = W - 1; x >= 0; --x){
        //        if(S[y][x] == '.')ma = x;
        //        smin(res[y][x], ma - x);
        //    }
        //}

        //rep(x, W){
        //    int mi = 0, ma = H - 1;
        //    rep(y, H){
        //        if(S[y][x] == '.')mi = y;
        //        smin(res[y][x], y - mi);
        //    }
        //    for(int y = H - 1; y >= 0; --y){
        //        if(S[y][x] == '.')ma = y;
        //        smin(res[y][x], ma - y);
        //    }
        //}

        /*
        set<int> yy, xx;
        rep(y, H)rep(x, W){
            if(S[y][x] == '.'){
                yy.insert(y);
                xx.insert(x);
            }
        }

        int ans = 0;

        rep(y, H){
            rep(x, W){
                if(S[y][x] == '#'){
                    int val = 0;
                    {
                        auto it = lower_bound(all(yy), y);
                        if(*it == y)++it;
                        smax(val, *it - y);
                        --it;
                        if(*it == y)--it;
                        smax(val, y - *it);
                    }
                    {
                        auto it = lower_bound(all(xx), x);
                        if(*it == x)++it;
                        smax(val, *it - x);
                        --it;
                        if(*it == x)--it;
                        smax(val, x - *it);
                    }
                    smax(ans, val);
                }
            }
        }
        */
    }
}
0