結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
|
提出日時 | 2016-07-23 00:39:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 767 ms / 3,000 ms |
コード長 | 1,568 bytes |
コンパイル時間 | 1,196 ms |
コンパイル使用メモリ | 89,736 KB |
実行使用メモリ | 158,792 KB |
最終ジャッジ日時 | 2024-11-06 12:52:36 |
合計ジャッジ時間 | 5,387 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream>#include <cstdio>#include <vector>#include <algorithm>#include <utility>#include <string>#include <queue>#include <tuple>using namespace std;typedef tuple<int, int, int> TUP;const vector<int> dx = {1, 1, 0, -1, -1, -1, 0, 1};const vector<int> dy = {0, 1, 1, 1, 0, -1, -1, -1};const int INF = 1e9;void show(vector<vector<int>> &v) {cout <<"---------" << endl;for (auto vv : v) {for (auto vvv : vv) {if (vvv == INF) {printf("- ");} else {printf("%d ", vvv);}}printf("\n");}}int main() {int h, w;cin >> h >> w;vector<string> s(h);for (int i = 0; i < h; i++) {cin >> s[i];}vector<vector<int>> t(h, vector<int>(w,INF));queue<TUP> que;for (int i = 0; i < h; i++) {que.push(make_tuple(-1, i, 0));que.push(make_tuple( w, i, 0));}for (int i = 0; i < w; i++) {que.push(make_tuple(i, -1, 0));que.push(make_tuple(i, h, 0));}for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (s[i][j] == '.') {que.push(make_tuple(j, i, 0));t[i][j] = 0;}}}int ans = 0;while (!que.empty()) {auto tup = que.front();que.pop();int x = get<0>(tup);int y = get<1>(tup);int v = get<2>(tup);int nv = v + 1;for (int i = 0; i < 8; i++) {int nx = x + dx[i];int ny = y + dy[i];if (nx < 0 || w <= nx || ny < 0 || h <= ny) {continue;}if (nv < t[ny][nx]) {t[ny][nx] = nv;que.push(make_tuple(nx, ny, nv));ans = max(ans, nv);}}}// show(t);cout << ans << endl;return 0;}