AOJ 1155 - Cliff Climbing

問題概要

Jackが崖を登る。崖はH×Wの二次元グリッドで表される。Jackは両足を交互に動かし崖を登る。つまり、左足を置いた後は右足を動かし、右足を置いた後は左足を動かす。

グリッドは以下の要素で構成される。

• 'S' : スタート位置(必ず崖の一番下のH-1行目に1つ以上存在する。)
• 'T' : ゴール位置(必ず崖の一番上の0行目に1つ以上存在する。)
• 'X' : 足を置くことのできないマス。
• '1'-'9' : t単位時間を必要とするマス。

足の動かし方はlx<rxかつ|lx-rx|+|ly-ry|≤3を満たす9パターンがある。
最初に'S'のマスに左足か右足を置くことからスタートし、ゴールへ到達するための最短時間を求めよ。到達できない場合は-1を出力せよ。

制約

• 2 ≤ W ≤ 30
• 5 ≤ H ≤ 60

解法

dijkstra。
実装が少し重い

感想

最初、両足の状態をメモしていたが、そのコードでACされた後、人のコードを見てメモしているのは片足だけであって確かになと思った。

コード

• 最初に提出したコード(両足メモ, 0.41sec)。

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_H 61
#define MAX_W 31
#define INF 1e9
#define Fi first
#define Se second
typedef pair<int,int> pii;
 
struct State{
  int d,lx,ly,rx,ry;
  bool f;
  State(){}
  State(int d,int lx,int ly,int rx,int ry,bool f) :
    d(d),lx(lx),ly(ly),rx(rx),ry(ry),f(f) {}
  bool operator > (const State &s)const{
    return d > s.d;
  }
};
 
int W,H;
int ps,pt;
pii S[MAX_W],T[MAX_W];
char field[MAX_H][MAX_W];
int dist[MAX_H][MAX_W][MAX_H][MAX_W][2];
 
const int dx[9] = {1,1,1,1,1,2,2,2,3};
const int dy[9] = {-2,-1,0,1,2,-1,0,1,0};
 
bool inField(int x,int y){
  return 0 <= x && x < W && 0 <= y && y < H;
}
 
int dijkstra(){
  priority_queue<State,vector<State>,greater<State> > Q;
  fill(dist[0][0][0][0],dist[0][0][0][0]+MAX_H*MAX_W*MAX_H*MAX_W*2,INF);
  for(int i = 0 ; i < ps ; i++){
    Q.push(State(0,S[i].Fi,S[i].Se,W,H,0)); 
    Q.push(State(0,W,H,S[i].Fi,S[i].Se,1));
    dist[S[i].Se][S[i].Fi][H][W][0] = 0;
    dist[H][W][S[i].Se][S[i].Fi][1] = 0;
  }
 
  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    int lx = s.lx, ly = s.ly;
    int rx = s.rx, ry = s.ry;
 
    if(dist[ly][lx][ry][rx][s.f] < s.d) continue;
    for(int i = 0 ; i < pt ; i++){
      if(lx == T[i].Fi && ly == T[i].Se ||
         rx == T[i].Fi && ry == T[i].Se){
        return s.d;
      }
    }
    if(s.f){
      for(int i = 0 ; i < 9 ; i++){
        int nlx = rx - dx[i];
        int nly = ry + dy[i];
        if(!inField(nlx,nly)) continue;
        if(field[nly][nlx] == 'X') continue;
        int t = field[nly][nlx] - '0';
        if(s.d + t < dist[nly][nlx][ry][rx][0]){
          dist[nly][nlx][ry][rx][0] = s.d + t;
          Q.push(State(dist[nly][nlx][ry][rx][0],nlx,nly,rx,ry,0));
        }
      }
    }else{
      for(int i = 0 ; i < 9 ; i++){
        int nrx = lx + dx[i];
        int nry = ly + dy[i];
        if(!inField(nrx,nry)) continue;
        if(field[nry][nrx] == 'X') continue;
        int t = field[nry][nrx] - '0';
        if(s.d + t < dist[ly][lx][nry][nrx][1]){
          dist[ly][lx][nry][nrx][1] = s.d + t;
          Q.push(State(dist[ly][lx][nry][nrx][1],lx,ly,nrx,nry,1));
        }
      }
    }
  }
  return -1;
}
 
int main(){
  dijkstra();
  while(cin >> W >> H, W){
    ps = pt = 0;
    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++){
        cin >> field[i][j];
        if(field[i][j] == 'S'){
          S[ps++] = pii(j,i);
          field[i][j] = '0';
        }else if(field[i][j] == 'T'){
          T[pt++] = pii(j,i);
          field[i][j] = '0';      
        }
      }
    }
    cout << dijkstra() << endl;
  }
  return 0;
}

• 次に提出したコード(片足メモ, 0.01sec)

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_H 61
#define MAX_W 31
#define INF 1e9
#define Fi first
#define Se second
typedef pair<int,int> pii;
 
struct State{
  int d,x,y;
  bool f;
  State(){}
  State(int d,int x,int y,bool f) :
    d(d),x(x),y(y),f(f) {}
  bool operator > (const State &s)const{
    return d > s.d;
  }
};
 
int W,H;
int ps,pt;
pii S[MAX_W],T[MAX_W];
char field[MAX_H][MAX_W];
int dist[MAX_H][MAX_W][2];
 
const int dx[9] = {1,1,1,1,1,2,2,2,3};
const int dy[9] = {-2,-1,0,1,2,-1,0,1,0};
 
bool inField(int x,int y){
  return 0 <= x && x < W && 0 <= y && y < H;
}
 
int dijkstra(){
  priority_queue<State,vector<State>,greater<State> > Q;
  fill(dist[0][0],dist[0][0]+MAX_H*MAX_W*2,INF);
  for(int i = 0 ; i < ps ; i++){
    Q.push(State(0,S[i].Fi,S[i].Se,0)); 
    Q.push(State(0,S[i].Fi,S[i].Se,1));
    dist[S[i].Se][S[i].Fi][0] = 0;
    dist[S[i].Se][S[i].Fi][1] = 0;
  }
 
  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    int x = s.x, y = s.y;
 
    if(dist[y][x][s.f] < s.d) continue;
    for(int i = 0 ; i < pt ; i++){
      if(x == T[i].Fi && y == T[i].Se){
        return s.d;
      }
    }
    if(s.f){
      for(int i = 0 ; i < 9 ; i++){
        int nx = x - dx[i];
        int ny = y + dy[i];
        if(!inField(nx,ny)) continue;
        if(field[ny][nx] == 'X') continue;
        int t = field[ny][nx] - '0';
        if(s.d + t < dist[ny][nx][0]){
          dist[ny][nx][0] = s.d + t;
          Q.push(State(dist[ny][nx][0],nx,ny,0));
        }
      }
    }else{
      for(int i = 0 ; i < 9 ; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!inField(nx,ny)) continue;
        if(field[ny][nx] == 'X') continue;
        int t = field[ny][nx] - '0';
        if(s.d + t < dist[ny][nx][1]){
          dist[ny][nx][1] = s.d + t;
          Q.push(State(dist[ny][nx][1],nx,ny,1));
        }
      }
    }
  }
  return -1;
}
 
int main(){
  dijkstra();
  while(cin >> W >> H, W){
    ps = pt = 0;
    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++){
        cin >> field[i][j];
        if(field[i][j] == 'S'){
          S[ps++] = pii(j,i);
          field[i][j] = '0';
        }else if(field[i][j] == 'T'){
          T[pt++] = pii(j,i);
          field[i][j] = '0';      
        }
      }
    }
    cout << dijkstra() << endl;
  }
  return 0;
}