はやし屋

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

AOJ 0234: Aizu Buried Treasure

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

いったとこビットで保存しておいて適当に再帰する。
階層が変わる(y座標+1になる)ごとにbitを0にします。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

int w , h;
int stage[11][11];
int RET;
int f , m , o;


int d[11][11][55];
void solve(int bit , int y , int x , int oxy , int cost){
  if(oxy <= 0)return ;
  if(!((bit>>x)&1)){
    if(stage[y][x] > 0)oxy = min(m,oxy+stage[y][x]);
    if(stage[y][x] < 0)cost += -stage[y][x];
    bit |= 1 << x;
  }
  if(cost>f)return ;
  if(d[y][x][oxy]<=cost)return;
  d[y][x][oxy] = cost;
  if(y == h-1){
    RET = min(RET,cost);
    return ;
  }
  solve(0,y+1,x,oxy-1,cost);
  if(x+1 < w )solve(bit,y,x+1,oxy-1,cost);
  if(x-1 >= 0)solve(bit,y,x-1,oxy-1,cost);
}

int main(){
  while(cin >> w >> h && (w|h)){
      for(int i = 0 ; i < 10 ; ++i)
	for(int k = 0 ; k < 10 ; ++k)
	  for(int u = 0 ; u < 55 ; ++u)
	    d[i][k][u] = 1 << 28;


    cin >> f >> m >> o;
    for(int i = 0 ; i < h ; ++i){
      for(int j = 0 ; j < w ; ++j){
	cin >> stage[i][j];
      }
    }
    RET = 1<<28;
    for(int i = 0 ; i < w ; ++i){
      solve(0,0,i,o-1,0);
    }
    if(RET == 1<<28)cout << "NA" << endl;
    else cout << RET << endl;
  }
}