AOJ2083 Black Force - nanikakaのAOJ航海日誌

概要

H*Wのグリッドで表される凹凸の土地が与えられる。(i, j)の高さはH(i,j)である。
ここに容量C以上の水を蓄えるダムを建てたい。グリッドの中からダムにするための土地を連続領域として選ぶ。連続領域とは、領域内の任意の2マス間を上下左右の移動のみを用いてかつ連続領域内のマスのみを通って行き来可能であるものをいう。ある連続領域のダムに蓄えることができる水の量は、[領域の外側に隣接する山の最小の高さ]-[連続領域の各マスの高さ]の総和である。高さの差1につき、水を1蓄えられる。連続領域がグリッドの外側と隣接している場合や、連続領域内から外側に水が漏れる場合(高さが一緒の場合も漏れ出ることになる)、水は貯められない。
また、この土地にはR個の先住民がおり、彼らの土地は連続領域に含めることができない。
更に、先住民がいないマスのうち最大1つまで、高さを1上げる工事を行うことができる。
この条件のもとで、目的のダムを作ることが可能か判定せよ。
0 < H, W <= 20

解法

深さ優先探索+枝刈りです。
連続領域を囲む山の高さの最小値をLと決めます。Lを決めるとマス(i, j)が連続領域になるかどうかが一意に決まります。Lを決め、未訪問のマス(i,j)でH(i,j) < Lならそれは連続領域に含まれるはずです。こうして連続領域を広げて行き、最終的に水をためられる形になったらダムの容量をチェックします。この流れをf(L)とします。
まず、高さを1上げる工事を行わない場合を考えます。つまり、H*Wのグリッドに登場する高さの集合に対して、f(L)を呼び出します。
次に、高さを1上げる工事について全通り試します。もちろん先住民のマスについては行いません。そして、f(H(i,j)+1)のみを呼び出します。(i,j)について工事を行ったのだから、H(i,j)+1についてだけチェックすればよいのです。他の値についてf(L)を呼び出しても、結果は変わりません。
あとは、f(L)の処理について無駄を極力省けば解くことができます。

ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Black Force
public class AOJ2083 {

	int h, w, c, val;
	int[][] a, d = {{-1,0},{0,1},{1,0},{0,-1}};
	boolean res, valid;
	boolean[][] v, b;

	void f(int L){
		v = new boolean[h][w];
		for(int i=1;i<h-1;i++)for(int j=1;j<w-1;j++){
			if(!v[i][j]&&a[i][j]<L){
				valid = true;
				val = 0;
				dfs(i, j, L);
				if(valid&&c<=val){
					res = true; return;
				}
			}
		}
	}

	void dfs(int i, int j, int L){
		if(v[i][j]||L<=a[i][j])return;
		v[i][j] = true;
		val += L-a[i][j];
		if(b[i][j]||i==0||i==h-1||j==0||j==w-1)valid = false;
		for(int k=0;k<4;k++){
			int ni = i+d[k][0], nj = j+d[k][1];
			if(0<=ni&&ni<h&&0<=nj&&nj<w)dfs(ni, nj, L);
		}
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			h = sc.nextInt(); w = sc.nextInt(); c = sc.nextInt();
			int r = sc.nextInt();
			if((h|w|c|r)==0)break;
			a = new int[h][w];
			Set<Integer> set = new HashSet<Integer>();
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				int x = sc.nextInt();
				a[i][j] = x;
				set.add(x);
			}
			b = new boolean[h][w];
			while(r--!=0){
				b[sc.nextInt()-1][sc.nextInt()-1] = true;
			}
			res = false;
			for(int x:set){
				if(res)break;
				f(x);
			}
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				if(res)break;
				if(b[i][j])continue;
				a[i][j]++;
				f(a[i][j]);
				a[i][j]--;
			}
			System.out.println(res?"Yes":"No");
		}
	}

	public static void main(String[] args) {
		new AOJ2083().run();
	}
}