結果

問題 No.402 最も海から遠い場所
ユーザー paruki
提出日時 2016-07-22 23:18:59
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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);
}
}
}
*/
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0