結果
問題 | No.402 最も海から遠い場所 |
ユーザー | moyashi_senpai |
提出日時 | 2016-07-23 00:55:05 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,557 ms / 3,000 ms |
コード長 | 2,094 bytes |
コンパイル時間 | 759 ms |
コンパイル使用メモリ | 80,616 KB |
実行使用メモリ | 499,284 KB |
最終ジャッジ日時 | 2023-08-06 11:02:17 |
合計ジャッジ時間 | 10,421 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 202 ms
426,188 KB |
testcase_01 | AC | 203 ms
426,068 KB |
testcase_02 | AC | 203 ms
426,220 KB |
testcase_03 | AC | 210 ms
426,136 KB |
testcase_04 | AC | 141 ms
426,364 KB |
testcase_05 | AC | 138 ms
426,064 KB |
testcase_06 | AC | 139 ms
426,120 KB |
testcase_07 | AC | 140 ms
426,128 KB |
testcase_08 | AC | 141 ms
426,076 KB |
testcase_09 | AC | 141 ms
426,128 KB |
testcase_10 | AC | 141 ms
426,152 KB |
testcase_11 | AC | 141 ms
426,228 KB |
testcase_12 | AC | 140 ms
426,056 KB |
testcase_13 | AC | 146 ms
426,388 KB |
testcase_14 | AC | 145 ms
426,168 KB |
testcase_15 | AC | 175 ms
427,112 KB |
testcase_16 | AC | 183 ms
427,496 KB |
testcase_17 | AC | 747 ms
443,788 KB |
testcase_18 | AC | 1,557 ms
430,060 KB |
testcase_19 | AC | 755 ms
499,284 KB |
testcase_20 | AC | 1,200 ms
426,172 KB |
testcase_21 | AC | 840 ms
462,788 KB |
ソースコード
#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; }