はやし屋

競技プログラミングのメモ きたない

AOJ 1150: Cliff Climbing

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150&lang=jp

Dijkstraっぽい

移動できるマスのおおまかな条件は、
"十字方向に移動すると考えた時3歩以内で行けるところ"でかつ"足の内側"
なのでテーブル使わなくても適当にforを回すとできる。

三項演算子使ったりrep使ったりするときたないです

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
using namespace std;

#define fr first
#define sc second
#define reps(i,j,n) for(int i = j ; i < n ; ++i)
#define rep(i,n) reps(i,0,n)

typedef pair < int , int > Pi;
typedef pair <  Pi , Pi  > Pii;
typedef priority_queue < Pii , vector < Pii > , greater < Pii > > Que;

int w , h;

char st[111][111];

bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}

int dijkstra(Que&que){
  int vis[2][111][111] = {};
  while(!que.empty()){
    Pii pi = que.top();que.pop();
    int cost = pi.fr.fr,turn = pi.fr.sc;
    int    y = pi.sc.fr,   x = pi.sc.sc;
    if(st[y][x] == 'T')return cost;
    if(vis[turn][y][x]++)continue;
    const int s[] = {1,-3} , t[] = {3,-1};
    int ny , nx;
    reps(i,s[turn],t[turn]+1)reps(j,-2,2+1)
      if(abs(i)+abs(j)<=3)if(!isover(ny=y+j,nx=x+i))if(st[ny][nx]!='X'){
	    int x = st[ny][nx];
	    que.push(Pii(Pi(cost+(x=='T'?0:x-'0'),turn^1),Pi(ny,nx)));	    
      }
  }
  return -1;
}

int main(){
  while(cin >> w >> h && (w|h)){
    Que que;
    rep(i,h)rep(j,w){
      cin >> st[i][j];
      if(st[i][j] == 'S')rep(turn,2)que.push(Pii(Pi(0,turn),Pi(i,j)));
    }
    cout << dijkstra(que) << endl;
  }
  return 0;
}