ACM/ICPC Live Archive 5066

幅優先探索 動的計画法

問題概要

三次元のマップが与えられます.

  • 'S' : 出入り口
  • 'X' : 壁
  • '.' : 歩ける場所
  • 'U' : 上の階へ上がれる場所
  • 'D' : 下の階へ下がれる場所

建物の中に, 助けを求めている人がN人います. それぞれ, 助けるともらえるポイントpiがついています.
ある消防士がいて, なるべく点数が高くなるように救出を行いたいと思っています.
S秒の時間制限があるとき, 救出の最高点数はいくらでしょう.
消防士は, 歩くたびに1秒消費し, 人を背負っている場合は2秒消費します.
人は, 一度に一人しか背負うことができず, 救出したい場合は一旦入り口まで運ぶ必要があります.

アルゴリズム

幅優先探索によって, スタートから全ての点までの最短距離を先に求めておきます.
あとは, ナップサック問題のごとく解くだけです.(動的計画法)

プログラム

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

class State{
public:
  int x,y,z;
  State(){}
  State(int _x,int _y,int _z){x=_x;y=_y;z=_z;}
};

int f,h,w,n,s;
int sx,sy;
int weight[102],price[102];
int dist[12][102][102];
int dp[102][10002];
char t[12][102][102];

int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};

void mkDist(){
  queue<State> open;
  open.push(State(sx,sy,0));
  memset(dist,-1,sizeof(dist));
  dist[0][sy][sx] = 0;

  while(!open.empty()){
    State st = open.front(); open.pop();

    rep(i,4){
      int nx = st.x + dx[i];
      int ny = st.y + dy[i];
      if(nx>=0 && w>nx && ny>=0 && h>ny && t[st.z][ny][nx]!='X' && dist[st.z][ny][nx]==-1){
        dist[st.z][ny][nx] = dist[st.z][st.y][st.x] + 1;
        open.push(State(nx,ny,st.z));
      }
    }

    if(t[st.z][st.y][st.x]=='U' && dist[st.z+1][st.y][st.x]==-1){
      dist[st.z+1][st.y][st.x] = dist[st.z][st.y][st.x] + 1;
      open.push(State(st.x,st.y,st.z+1));
    }
    else if(t[st.z][st.y][st.x]=='D' && dist[st.z-1][st.y][st.x]==-1){
      dist[st.z-1][st.y][st.x] = dist[st.z][st.y][st.x] + 1;
      open.push(State(st.x,st.y,st.z-1));
    }
  }
}

int main(){
  int T;
  scanf("%d",&T);

  while(T--){
    scanf("%d%d%d%d%d",&f,&h,&w,&n,&s);
    sx = sy = -1;

    rep(i,f){
      rep(j,h){
        scanf("%s",t[i][j]);

        if(sx!=-1) continue;
        rep(k,w){
          if(t[i][j][k] == 'S'){
            sx = k;
            sy = j;
            break;
          }
        }
      }
    }

    mkDist();

    rep(i,n){
      int x,y,z;
      scanf("%d%d%d%d",&z,&y,&x,&price[i]);
      weight[i] = dist[z-1][y-1][x-1] * 3;
    }

    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    rep(i,n){
      rep(j,s+1){
        if(dp[i][j] != -1){
          if(weight[i] >= 0){
            int nw = j + weight[i];
            int np = dp[i][j] + price[i];
            if(nw <= s && (dp[i+1][nw] == -1 || np > dp[i+1][nw])){
              dp[i+1][nw] = np;
            }
          }

          if(dp[i+1][j] == -1 || dp[i][j] > dp[i+1][j]){
            dp[i+1][j] = dp[i][j];
          }
        }
      }
    }

    int ans = 0;
    rep(i,s+1){
      if(ans < dp[n][i]){
        ans = dp[n][i];
      }
    }
    printf("%d\n",ans);
  }
}