AOJ1156 Twirling Robot

Problem

唐突に収束するまで回したい欲に駆られたので書いてみた。

Source

ACM/ICPC Japan Domestic Contest 2008: Problem D

Description

ロボットを最小コストでゴールまで導け。与えられたコストで方向転換+移動が出来る他に、マスごとに指定された1方向へはコスト0で転換できる。

Solution

拡張グラフでの最短経路をBellman-Fordで求める感じで。

Code

#include <iostream>
#include <algorithm>

#define REP(i,e) for(int i=0;i<(int)(e);i++)

using namespace std;

enum{ N=32, inf=1<<20 };

int li,lj;
int field[N][N];
int op[4];

int compute(){
  static int cost[N][N][4];
  REP(i,li) REP(j,lj) REP(d,4) cost[i][j][d]=inf;
  cost[0][0][1]=0;

  const int DI[]={-1,0,1,0};
  const int DJ[]={0,1,0,-1};

  while(true){
    bool f=true;
    REP(i,li) REP(j,lj) REP(d,4) REP(o,4){
        int nd=(d+o)%4;
        int ni=i+DI[nd], nj=j+DJ[nd],
          nc=cost[i][j][d]+(o==field[i][j]?0:op[o]);
        if(0<=ni&&ni<li&&0<=nj&&nj<lj && cost[ni][nj][nd]>nc)
          cost[ni][nj][nd]=nc, f=false;
    }
    if(f) break;
  }
  return *min_element(cost[li-1][lj-1],cost[li-1][lj-1]+4);
}

main(){
  while(cin >> lj >> li && li|lj){
    REP(i,li) REP(j,lj) cin >> field[i][j];
    REP(i,4) cin >> op[i];
    cout << compute() << endl;
  }
}

Notes

  • すっきりしていていい感じです。
  • 辛うじてAOJでの最短コード達成・・・したけど、どうやら前により速いプログラムでAC貰ってたみたいなので、ランキングには載りませんでした。
  • 他にやらなければならないことがあるときほど、プログラムを書く手は進むものです。