結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-23 00:55:05 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,840 ms / 3,000 ms |
コード長 | 2,094 bytes |
コンパイル時間 | 1,398 ms |
コンパイル使用メモリ | 85,396 KB |
実行使用メモリ | 499,796 KB |
最終ジャッジ日時 | 2024-11-06 14:06:24 |
合計ジャッジ時間 | 16,713 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:26:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 26 | scanf("%d %d%*c", &h, &w); | ~~~~~^~~~~~~~~~~~~~~~~~~~ main.cpp:33:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 33 | scanf("%c", &c); | ~~~~~^~~~~~~~~~ main.cpp:40:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | scanf("%*c"); | ~~~~~^~~~~~~
ソースコード
#include <iostream>#include <cstdio>#include <vector>#include <cmath>#include <cstring>#include <numeric>#include <algorithm>#include <functional>#include <array>#include <map>#include <queue>using namespace std;#define Getsign(n) ((n > 0) - (n < 0))typedef vector<int> Ivec;typedef pair<int, int> Pos;const pair<int, int> dir[8] = { {0,1},{1,1}, {1,0},{0,-1},{-1,-1},{1,-1},{-1,1}, {-1,0} };#define MAX(a,b) (((a)>(b))?(a):(b))#define Chebi(a,b) (MAX(abs(a.first-b.first),abs(a.second-b.second)))int main() {int h, w;scanf("%d %d%*c", &h, &w);int map[3004][30004] = {};Pos poss[3004][3004];queue<Pos> wf;for (int i = 2; h + 1 >= i; i++) {for (int j = 2; w + 1 >= j; j++) {char c;scanf("%c", &c);map[i][j] = c == '#' ? 1 : 0;if (c == '.') {wf.push({ i,j });poss[i][j] = { i,j };}}scanf("%*c");}for (int i = 1; h + 2 >= i; i++) {wf.push({ i, 1 });wf.push({ i, w+2 });poss[i][1] = { i,1 };poss[i][w+2] = {i, w + 2 };}for (int i = 1; w + 2 >= i; i++) {wf.push({ 1,i });wf.push({h+2,i });poss[1][i] = { 1,i};poss[h+2][i] = {h + 2,i};}while (!wf.empty()) {Pos sea = wf.front();wf.pop();for (int i = 0; 8 > i; i++) {Pos tar = { sea.first + dir[i].first ,sea.second + dir[i].second };if (map[tar.first][tar.second] == 1) {if (poss[tar.first][tar.second].first == 0 || (Chebi(tar, poss[sea.first][sea.second]) < Chebi(tar, poss[tar.first][tar.second]))) {if (poss[tar.first][tar.second].first == 0 || poss[tar.first][tar.second].first != poss[sea.first][sea.second].first || poss[tar.first][tar.second].second != poss[sea.first][sea.second].second){poss[tar.first][tar.second] = poss[sea.first][sea.second];wf.push(tar);}}}}}int maxim = -1, maxss[3004][3004] = {};for (int i = 2; h + 1 >= i; i++) {for (int j = 2; w + 1 >= j; j++) {if (map[i][j] != 1)continue;Pos tar = { i,j };maxss[i][j] = Chebi(poss[i][j], tar);maxim = max(maxim, Chebi(poss[i][j], tar));}}printf("%d", maxim);return 0;}