AOJ2302 On or Off

AOJ Volume23

問題リンク On or Off

  • 概要

大きさR*Cのグリッドのオフィスがある。任意の部屋の対について、それらの部屋間を移動する方法は必ず1通りしかない。
M個の仕事をする必要があり、その仕事をするための部屋(r, c)が決まっている。仕事はその部屋についた瞬間終わらすことができる。部屋を1つ移動するには1の時間がかかる。
オフィスの各部屋は最初は電気がついていない。部屋に入ってきたとき、電気がついていない場合は電気をつけなくてはならない。また、部屋を出るとき、電気を消すか付けっぱなしにするかを選択することができる。電気を付けるためのコスト、消すためのコスト、電気がついているとき単位時間に消費する電気コストの情報が、各部屋について与えられる。全ての仕事を終わらせるために必要なコストの最小値を答えよ。ただし、仕事を全て終わらせたとき、電気がつけっぱなしになっている部屋があってはならない。
0 < R, C <= 50
2 <= M <= 1000

  • 解法

DPの方針で解きます。
i番目の仕事をする場所からi+1番目の仕事をする場所への移動方法はユニークに決まるため、仕事全体を通して部屋を訪れる順番は一意に決まります。
部屋(r, c)に進入するとき、電気をつける場合と、つけなくていい場合があります。つける場合は、その部屋の訪問が最初の場合か、前回訪れたときに電気を消して部屋を出た場合のどちらかです。つけなくていい場合は、前回訪問時に電気を付けっぱなしにして部屋を出た場合です。最初の訪問の場合は電気をONにするコストが必ずかかりますが、2回目以降の訪問のときには、前回の部屋を出る際の振る舞いのうち、得になる方を選ぶことができます。もし、電気を消していたならば、電気をoffにするコストと、onにするコストがかかります。電気をつけっぱなしにしていたら、現在の時刻と前回訪れたときの時刻の差分だけ、消費電力コストがかかります。よって、これらを計算するために、
dp[r][c]: 部屋(r, c)に進入したとき電気が付いているための最小コスト
v[r][c]: 最後に訪れた時間
の情報が必要になります。最初の訪問時は
dp[r][c] = ONのためのコスト
となり、2回目以降は
dp[r][c] = min{前回消していた場合, 前回付けっぱなしにした場合}
です。
前回消していた場合 = dp[r][c] + OFFのコスト + ONのコスト
つけっぱなしの場合 = dp[r][c] + (nowtime - v[r][c])*消費電力コスト
となります。
最終的には、どの部屋もOFFのコストがかかるので、1回以上訪問した部屋のOFFのコストを更に加算して解が計算できます。

部屋(r, c)から部屋(r2, c2)へ移動する方法はユニークなのですが、では具体的にどう動けばいいのかを調べるのは地味に難しいです。自分は、深さ優先探索をして経路復元のための表を毎度作る方法を取りました。

  • ソース
import java.util.Scanner;

//On or Off
public class AOJ2302 {

	int h, w, M;
	int[][] cost, on, off, nh, nw, v, dp;
	char[][] map;
	int[][] move = {{-1,0},{0,1},{1,0},{0,-1}};
	boolean[][] u;
	
	boolean dfs(int i, int j, int ti, int tj){
		if(i==ti&&j==tj)return true;
		u[i][j] = true;
		for(int k=0;k<4;k++){
			int ni = i+move[k][0], nj = j+move[k][1];
			if(0<=ni&&ni<h&&0<=nj&&nj<w&&!u[ni][nj]&&map[ni][nj]=='.'){
				if(dfs(ni, nj, ti, tj)){
					nh[i][j] = ni; nw[i][j] = nj; return true;
				}
			}
		}
		nh[i][j] = nw[i][j] = -1;
		return false;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		h = sc.nextInt(); w = sc.nextInt(); M = sc.nextInt();
		cost = new int[h][w];
		on = new int[h][w]; off = new int[h][w];
		nh = new int[h][w]; nw = new int[h][w];
		map = new char[h][w];
		for(int i=0;i<h;i++)map[i]=sc.next().toCharArray();
		v = new int[h][w];
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)v[i][j] = -1;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)cost[i][j]=sc.nextInt();
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)on[i][j]=sc.nextInt();
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)off[i][j]=sc.nextInt();
		int t = 0, pi = sc.nextInt(), pj = sc.nextInt();
		dp = new int[h][w];
		v[pi][pj] = 0;
		dp[pi][pj] = on[pi][pj];
		while(--M!=0){
			int ti = sc.nextInt(), tj = sc.nextInt();
			u = new boolean[h][w];
			dfs(pi, pj, ti, tj);
			for(;pi!=ti||pj!=tj;){
				int ni = nh[pi][pj], nj = nw[pi][pj];
				t++;
				if(v[ni][nj]==-1)dp[ni][nj] = on[ni][nj];
				else dp[ni][nj] = Math.min(dp[ni][nj]+off[ni][nj]+on[ni][nj], dp[ni][nj]+(t-v[ni][nj])*cost[ni][nj]);
				v[ni][nj] = t;
				pi = ni; pj = nj;
			}
		}
		int res = 0;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(v[i][j]!=-1)res+=dp[i][j]+off[i][j];
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new AOJ2302().run();
	}
}