結果

問題 No.402 最も海から遠い場所
ユーザー parukiparuki
提出日時 2016-07-22 23:18:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,085 ms / 3,000 ms
コード長 3,367 bytes
コンパイル時間 1,952 ms
コンパイル使用メモリ 181,112 KB
実行使用メモリ 483,428 KB
最終ジャッジ日時 2024-11-06 13:12:41
合計ジャッジ時間 7,374 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
12,508 KB
testcase_01 AC 5 ms
12,288 KB
testcase_02 AC 6 ms
12,544 KB
testcase_03 AC 5 ms
12,416 KB
testcase_04 AC 6 ms
12,276 KB
testcase_05 AC 6 ms
12,288 KB
testcase_06 AC 6 ms
12,288 KB
testcase_07 AC 5 ms
12,288 KB
testcase_08 AC 5 ms
12,476 KB
testcase_09 AC 5 ms
12,404 KB
testcase_10 AC 5 ms
12,328 KB
testcase_11 AC 5 ms
12,416 KB
testcase_12 AC 6 ms
12,288 KB
testcase_13 AC 11 ms
14,080 KB
testcase_14 AC 8 ms
12,788 KB
testcase_15 AC 38 ms
21,632 KB
testcase_16 AC 47 ms
22,784 KB
testcase_17 AC 592 ms
187,840 KB
testcase_18 AC 1,085 ms
71,764 KB
testcase_19 AC 951 ms
483,428 KB
testcase_20 AC 731 ms
48,148 KB
testcase_21 AC 798 ms
376,024 KB
権限があれば一括ダウンロードができます

ソースコード

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));

        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.front();
            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