PKU-3328, AOJ-1150: Cliff Climbing (崖登り)

keyword

Dijkstra　C++　Java

問題概要

W*H(W<30, H<60)のボードが与えられる。各セルには数字かXが入っている。右足と左足を交互に下ろしてある点からある点へ移動する最小コストを求める問題。コストはノードを通った回数だけ加算され、Xのセルには入れない。また、右足(左足)を下ろしているときは左側(右側)のマンハッタン距離3以下のセルにしか移動出来ない。

解法

また「DはDijkstraのD」の問題。どのマスにいるか、どの足を下ろしているかを状態としてDijkstraするだけ。ちなみにAOJでJavaを使っている理由は他にJavaの練習できるオンラインジャッジが少ないから(主にTLEが理由で)。

import java.util.*;
import static java.lang.Math.*;

public class Main {

	int w, h;
	int[][] board;
	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			w = in.nextInt(); h = in.nextInt();
			if(w==0 && h==0) return ;
			board = new int[h][w];
			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					String s = in.next();
					char c = s.charAt(0);
					if(Character.isDigit(c)){
						board[i][j] = c - '0';
					}
					else if(c == 'T'){
						board[i][j] = -1;
					}
					else if(c == 'S'){
						board[i][j] = -2;
					}
				}
			}
			System.out.println(solve());
		}
	}

	class State{
		int dist, x, y, foot;
		State(int _d, int _y, int _x, int _f){
			this.dist = _d;
			this.y = _y;
			this.x = _x;
			this.foot = _f;
		}
	}

	class Cmp implements Comparator<State>{
		public int compare(State a, State b){
			return a.dist>b.dist?1:a.dist<b.dist?-1:0;
		}
	}

	int solve(){
		PriorityQueue<State> Q = new PriorityQueue<State>(11,new Cmp())	;
		int[][][] dist = new int[2][h][w];
		for(int k=0; k<2; k++)
			for(int i=0; i<h; i++)
				for(int j=0; j<w; j++)
					dist[k][i][j] = -1;
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++)if(board[i][j] == -1){
				for(int k=0; k<2; k++)
					Q.add(new State(0,i,j,k));
			}
		}
		while(!Q.isEmpty()){
			State tp = Q.poll();
			if(dist[tp.foot][tp.y][tp.x] != -1) continue;
			dist[tp.foot][tp.y][tp.x] = tp.dist;
			for(int dx=1; dx<=3; dx++){
				for(int dy=-2; dy<=2; dy++)if(dx + abs(dy) <= 3){
					int ny = tp.y + dy, nx = tp.x + ((tp.foot==0)?dx:-dx);
					if(0<=ny && ny<h && 0<=nx && nx<w && board[ny][nx]!=0 && dist[1-tp.foot][ny][nx] == -1){
						Q.add(new State(tp.dist + (board[ny][nx]>0?board[ny][nx]:0), ny, nx, 1-tp.foot));
					}
				}
			}
		}
		
		int ret = 1<<20;
		for(int k=0; k<2; k++){
			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					if(board[i][j] == -2 && dist[k][i][j] != -1 && ret > dist[k][i][j])
						ret = dist[k][i][j];
				}
			}
		}
		return ret==1<<20?-1:ret;
	}

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

const int INF = 1<<29;

char board[70][40];
int dist[2][70][40];
int W,H;

struct state{
    int dist, y, x, foot;
    state(int a, int b, int c, int d):dist(a),y(b),x(c),foot(d){}
};

bool operator<(const state& a, const state& b){ return a.dist > b.dist; }

int solve(){
    for(int k=0; k<2; k++)for(int i=0; i<H; i++)for(int j=0; j<W; j++)
        dist[k][i][j] = INF;
    priority_queue<state> Q;
    for(int j=0; j<W; j++)if(board[H-1][j] == 'S'){
        Q.push(state(0,H-1,j,0));
        Q.push(state(0,H-1,j,1));
    }
    while(!Q.empty()){
        state tp = Q.top(); Q.pop();
        if(board[tp.y][tp.x] == 'T') return tp.dist;
        if(dist[tp.foot][tp.y][tp.x] != INF) continue;
        dist[tp.foot][tp.y][tp.x] = tp.dist;
        for(int dx=1; dx<=3; dx++)for(int dy=-2;dy<=2;dy++)if(dx+abs(dy)<=3){
            int ny = tp.y + dy, nx = tp.x + (tp.foot?dx:-dx), nf = 1-tp.foot;
            if(0<=ny&&ny<H&&0<=nx&&nx<W && board[ny][nx] != 'X' && dist[nf][ny][nx] == INF)
                Q.push(state(tp.dist+('1'<=board[ny][nx]&&board[ny][nx]<='9'?board[ny][nx]&15:0), ny, nx, nf));
        }
    }
    return -1;
}