結果

問題 No.402 最も海から遠い場所
コンテスト
ユーザー kapo
提出日時 2016-07-22 23:48:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,056 ms / 3,000 ms
コード長 2,152 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 78,612 KB
実行使用メモリ 112,056 KB
最終ジャッジ日時 2024-11-06 13:27:59
合計ジャッジ時間 6,075 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS // #pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <sstream>
#include <cmath>
using namespace std; 

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()

typedef pair<int, int> Pii;
typedef vector<int> V;
typedef long long ll;
const int inf = 2e9;
const int mod = 1e9 + 7;
const int MAX_N = 202020;

int A[3003][3003];
int H, W;
queue<Pii> Qe, Qo;
int dy[8] = {-1,-1,0,1,1,1,0,-1}; // u r d l
int dx[8] = {0,1,1,1,0,-1,-1,-1};

int main()
{
	cin >> H >> W;
	fill(A[0],A[H+2],9999);

	rep(i,0,H+2) { // tate
		A[i][0] = 0;
		Qo.push(mp(i,0));
		A[i][W+1] = 0;
		Qo.push(mp(i,W+1));
	}
	rep(i,0,W+2) { // yoko
		A[0][i] = 0;
		Qo.push(mp(0,i));
		A[H+1][i] = 0;
		Qo.push(mp(H+1,i));
	}
	rep(i,1,H+1) rep(j,1,W+1) {
		char c; cin >> c;
		if (c == '.') {
			A[i][j] = 0;
			Qo.push(mp(i,j));
		}
	}
	//rep(i,0,H+2) { rep(j,0,W+2) printf("%04d ",A[i][j]); cout << endl; } cout << endl;

	rep(i,1,max(H,W)+1) {
		if (i%2==0) { // Qe
			while(!Qe.empty()) {
				Pii P = Qe.front(); Qe.pop();
				int cy = P.first, cx = P.second;
				rep(j,0,8) {
					int ty = cy + dy[j];
					int tx = cx + dx[j];
					if (ty<0 || ty>H+1 || tx<0 || tx>W+1) continue;
					if (A[ty][tx] == 9999) {
						A[ty][tx] = i;
						Qo.push(mp(ty,tx));
					}
				}
			}
		}
		else { // Qo
			while(!Qo.empty()) {
				Pii P = Qo.front(); Qo.pop();
				int cy = P.first, cx = P.second;
				//printf("     cy=%d cx=%d\n",cy,cx);
				rep(j,0,8) {
					int ty = cy + dy[j];
					int tx = cx + dx[j];
					if (ty<0 || ty>H+1 || tx<0 || tx>W+1) continue;
					if (A[ty][tx] == 9999) {
						A[ty][tx] = i;
						Qe.push(mp(ty,tx));
						//if(i==1) printf("push ty=%d tx=%d\n",ty,tx);
					}
				}
			}
		//if (i==1) rep(i,0,H+2) { rep(j,0,W+2) printf("%04d ",A[i][j]); cout << endl; } cout << endl;
		}
	}
	//rep(i,0,H+2) { rep(j,0,W+2) printf("%04d ",A[i][j]); cout << endl; }

	int ans = 0;
	rep(i,0,H+2) rep(j,0,W+2) ans = max(ans, A[i][j]);
	cout << ans;

	return 0;
}
0