yukicoder : No.402 最も海から遠い場所

チェビシェフ距離っていう言い方が一番勉強になったかも。
https://yukicoder.me/problems/no/402

問題

海と陸を模した2次元グリッドが与えられる。
陸に相当するマスのうち、海に相当するマスまでのチェビシェフ距離の最大値を求めよ。

解法

ダイクストラの要領で解く。
海のマスをチェビシェフ距離0とし、そこから上下左右計８マスにコスト1で移動できると考えて、陸の各マスへの距離を求めていこう。

int H,W;
string S[3030];
int D[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	FOR(y,H) cin>>S[y+1], S[y+1]='.'+S[y+1]+'.';
	
	FOR(x,W+2) S[0]+='.', S[H+1]+='.';
	H+=2;
	W+=2;
	
	FOR(y,H) FOR(x,W) D[y][x]=3030;
	queue<int> Q;
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') D[y][x]=0, Q.push(y*10000+x);
	
	int ma=0;
	while(Q.size()) {
		k=Q.front();
		Q.pop();
		int cy=k/10000,cx=k%10000;
		FOR(i,9) {
			int ty=cy+(i/3-1);
			int tx=cx+(i%3-1);
			if(tx<0 || tx>=W || ty<0||ty>=H || D[ty][tx]<=D[cy][cx]+1) continue;
			ma=D[ty][tx]=D[cy][cx]+1;
			Q.push(ty*10000+tx);
		}
	}
	
	cout<<ma<<endl;
	
}

まとめ

これも★２ってことはないか。