Problem 0194 : Byakko Delivery Company - しおしおたのブログ

Problem 0194 : Byakko Delivery Company
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0194&lang=jp

問題概要

信号が切り替わったり、渋滞してたり、工事してたり、Uターンできなかったりするグリッドを
走る、止まることのできないトラックが目的地につくための最短コストを求める。

解法

全探索。とってもめんどくさい。
とくに入力がめんどくさかった。
あと、信号の解釈？がちがってなかなかできなかった。
トラックが倉庫を出発した瞬間、切り替わるっていうのは出発直後じゃなく、出発するのと同時にって意味らしく、つまった。難しく考えすぎた。
ソースはとっても汚くて見せられないレベル。
でも、見せる。

#include<iostream>
#include<algorithm>

using namespace std;
int tra[20][20],  cost[20][20][20][20], h, w, end1, end2;
int ty[]={-1, 1, 0, 0}, tx[]={0, 0, 1, -1}, ans;
bool visited[20][20][20][20][101];
void dfs(int y, int x, int now, int prey, int prex){
  visited[y][x][prey][prex][now] = true;
  if(now > 100)return;
  if(end1 == y && end2 == x){
    ans = min(ans, now);
    return;
  }
  for(int i=0; i<4; i++){
    int nx = x + tx[i], ny = y + ty[i];
    if(nx == prex && ny == prey)continue;
    if(nx < 0 || ny < 0 || nx >= w || ny >= h){
      continue;
    }
    
    if(cost[y][x][ny][nx] < 0){
      continue;
    }
    if(tra[ny][nx] != 0){
      int k = tra[ny][nx];
      if((now+cost[y][x][ny][nx])%(k*2) < k ){
	if(i==2 || i == 3){
	  continue;
	}
      }
      else if(i == 0 || i == 1){
	continue;
      }
    }

    if(visited[ny][nx][y][x][now+cost[y][x][ny][nx]]){
      continue;
    }
    dfs(ny, nx, now + cost[y][x][ny][nx], y, x);
  }
}
  
main(){


  while( cin >> h >> w ){
    if( h + w == 0){
      break;
    }

    int D;
    cin >> D;

    int tnum;
    cin >> tnum;
    
    fill(&tra[0][0], &tra[h-1][w], 0);
    for(int i=0; i<tnum; i++){
      char tmp, c;
      int tmp2;
      
      cin >> tmp >> c >> tmp2;
      tmp2--;
      cin >> tra[tmp-'a'][tmp2];
    }

    fill(&cost[0][0][0][0], &cost[h-1][w-1][h-1][w], D);

    int nc;
    cin >> nc;

    for(int i=0; i<nc; i++){
      char tmp, c,dst;
      int tmp2,dst2;
      
      cin >> tmp >> c >> tmp2 >> dst >> c >> dst2;
      tmp2--;
      dst2--;
      cost[tmp-'a'][tmp2][dst-'a'][dst2] = -1;
      cost[dst-'a'][dst2][tmp-'a'][tmp2] = -1;
    }

    int nj;
    cin >> nj;

    for(int i=0; i<nj; i++){
      char tmp, c,dst;
      int tmp2,dst2, d;
      
      cin >> tmp >> c >> tmp2 >> dst >> c >> dst2 >> d;
      tmp2--;
      dst2--;
      if(cost[tmp-'a'][tmp2][dst-'a'][dst2] < 0){
	continue;
      }
      cost[tmp-'a'][tmp2][dst-'a'][dst2] += d;
      cost[dst-'a'][dst2][tmp-'a'][tmp2] += d;
    }
    
    char tmp, c,goal;
    int tmp2,goal2;
    cin >> tmp >> c >> tmp2 >> goal >> c >> goal2;
    tmp2--;
    goal2--;
    end1 = goal-'a';
    end2 = goal2;
    ans = 500;
    fill(&visited[0][0][0][0][0], &visited[h-1][w-1][h-1][w-1][101], false);
    dfs(tmp-'a', tmp2, 0, 0, 0);

    cout << ans << endl;
  }
}

あまりにも、汚いと思う。
っていうか、入力のとき、いちいち変数を宣言し直すのはどうなんだろう。
変数はスコープ？を狭めれば狭める方がいいと某部員にいわれたんだけども。
これは読みにくいよね。
それに、now+cost[y][x][ny][nx]を多用してるんだから、それをなにかの変数でもてばよかった。
とにかく、汚いコードです。反省して次に生かします。

visitedが５次元配列になってますが、４次元でも解けます。
っていうかそのほうが適切です。
僕　visited[y][x][prey][prex][t] つまり、今の座標と前の座標、今の時間。
適切　visited[y][x][d][t] 　　　　前の座標を記憶せずにどこの方向からきたか記録するべき。