結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-24 12:33:57 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 587 ms / 3,000 ms |
コード長 | 1,566 bytes |
コンパイル時間 | 1,030 ms |
コンパイル使用メモリ | 72,696 KB |
実行使用メモリ | 156,256 KB |
最終ジャッジ日時 | 2024-11-06 15:49:13 |
合計ジャッジ時間 | 4,065 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
コンパイルメッセージ
main.cpp: In function ‘void input()’: main.cpp:28:48: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 28 | for (int i = 1; i < h - 1; i++) { scanf("%s", s[i] + 1); s[i][w-1] = '.'; } | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
//サンプルがやさしい(な阪関)#include <iostream>#include <algorithm>#include <tuple>#include <queue>#include <cstdio>using namespace std;int h, w;char s[3002][3002];int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};int cost[3002][3002];void input() {//番兵するcin >> h >> w;h += 2;w += 2;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {s[i][j] = '.';}}for (int i = 1; i < h - 1; i++) { scanf("%s", s[i] + 1); s[i][w-1] = '.'; }for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {cost[i][j] = 1145141919;}}}inline bool is_range(int y, int x) {return (0 <= y && y < h && 0 <= x && x < w);}void bfs() {typedef tuple<int, int, int> T; //cost, y, xstatic queue<T> que;//全ての海を始点にするfor (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (s[i][j] == '.') {que.push(T(0, i, j));cost[i][j] = 0;}}}while (!que.empty()) {T now = que.front();que.pop();int cst = get<0>(now);int y = get<1>(now);int x = get<2>(now);for (int dir = 0; dir < 8; dir++) {int ny = y + dy[dir];int nx = x + dx[dir];if (is_range(ny, nx) && cost[ny][nx] > cst + 1) {que.push(T(cst + 1, ny, nx));cost[ny][nx] = cst + 1;}}}}int answer() {int ans = -1;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {ans = max(ans, cost[i][j]);}}return ans;}int main() {input();bfs();cout << answer() << endl;return 0;}