結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-22 22:49:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 574 ms / 3,000 ms |
コード長 | 1,932 bytes |
コンパイル時間 | 1,171 ms |
コンパイル使用メモリ | 108,048 KB |
実行使用メモリ | 126,496 KB |
最終ジャッジ日時 | 2024-11-06 12:53:26 |
合計ジャッジ時間 | 4,142 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//#include<cctype>#include<climits>#include<iostream>#include<string>#include<vector>#include<map>//#include<list>#include<queue>#include<deque>#include<algorithm>//#include<numeric>#include<utility>//#include<memory>#include<functional>#include<cassert>#include<set>#include<stack>#include<random>const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};using namespace std;typedef long long ll;typedef unsigned long long ull;typedef vector<int> vi;typedef vector<ll> vll;typedef pair<int, int> pii;const int MAXH = 3333;const int INF = 1e9;string board[MAXH];int d[MAXH][MAXH];int main() {cin.tie(0);ios::sync_with_stdio(false);int H, W;cin >> H >> W;for (int i = 1; i <= H; i++) {string s;cin >> s;s = '.' + s + '.';board[i] = s;}H += 2;W += 2;{string s;for (int i = 0; i < W; i++)s += '.';board[0] = s;board[H-1] = s;}for (int i = 0; i < H; i++) for (int j = 0; j < W; j++)d[i][j] = INF;queue<pii> que;for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {if (board[i][j] == '.') {d[i][j] = 0;que.push(pii(i, j));}}while (!que.empty()) {auto p = que.front(); que.pop();int y = p.first, x = p.second;for (int i = 0; i < 8; i++) {int ny = y+dy[i], nx = x+dx[i];if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;if (d[ny][nx] > d[y][x] + 1) {d[ny][nx] = d[y][x] + 1;que.push(pii(ny, nx));}}}int ans = 0;for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {ans = max(ans, d[i][j]);}cout << ans << endl;return 0;}