AOJ 0245 Time Sale

問題文

Time Sale

感想

なんか探索多いけど、これもその1つ。ただこれは状態の持ち方間違えなければ普通に間に合う。

もし時刻tを持てなかったら割りと実装が大変になるんですが、さすがにPCK優しいので楽。問題文うろ覚えている程度には知ってたので、昨日の練習会では15分くらいで実装できた。

解法

ある状態にたどり着けるかどうかだけ調べる全探索、状態の持ち方は箇条書きに。

幅優先で書いているがこの方針なら深さ優先でよいはず。

• ある時刻t(101通り)に今までどの商品を得ていて(2^8通り)どの座標にいるか(20*20通り)を全て持つ。1000万通りくらい。
• "今までどの商品を得ていて"というのはbitで管理する。
• 予め2^8通りのパターンについて計算しとくとあるbitで得れる割引の値というのはO(1)で求まるので適当にやった。
• 面倒くさい部分があるとしたら番号を0,1,2,...,って0から再割り振りしなきゃいけないところかな。

ソース

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
char c[22][22];
 
 
struct NODE{
    int x,y,bit,time;
    NODE(int x,int y,int bit,int time) : x(x) , y(y) , bit(bit) , time(time) {}
};
 
int num[10] , d[10] , s[10] , e[10];
int done[22][22][1<<8][102] = {};
 
int dx[] = {0,1,0,-1,0};
int dy[] = {1,0,-1,0,0};
int main(){
    int W,H;
    while(cin >> W >> H && W){
        rep(i,22)rep(j,22) c[i][j] = '#';
        queue<NODE> Q;
        for(int i = 0 ; i < H ; i++){
            for(int j = 0 ; j < W ; j++){
                cin >> c[i+1][j+1];
                if( c[i+1][j+1] == 'P'){
                    Q.push(NODE(j+1,i+1,0,0));
                    c[i+1][j+1] = '.';
                }
            }
        }
        int N;
        cin >> N;
        for(int i = 0 ; i < N ; i++){
            int g;
            cin >> g;
            num[g] = i;
            cin >> d[i] >> s[i] >> e[i];
        }
        int value[1<<10] = {};
        for(int i = 0 ; i < (1<<N) ; i++){
            for(int j = 0 ; j < N ; j++){
                value[i] += (i>>j&1) * d[j];
            }
            //cout << value[i] << " " << i << endl;
        }
         
        memset(done,0,sizeof(done));
        int ans = 0;
        while(Q.size()){
            NODE q = Q.front(); Q.pop();
            if( q.time > 100 ) continue;
            if( c[q.y][q.x] != '.' ) continue;
            for(int i = 0 ; i < 4 ; i++){
                int tx = q.x + dx[i];
                int ty = q.y + dy[i];
                if( c[ty][tx] >= '0' && c[ty][tx] <= '9' ){
                    int idx = num[c[ty][tx]-'0'];
                    if( s[idx] <= q.time && q.time < e[idx] ) q.bit |= 1<<idx;
                     
                }
            }
            if( done[q.x][q.y][q.bit][q.time]++ ) continue;
            ans = max( ans , value[q.bit] );
            for(int i = 0 ; i < 5 ; i++){
                Q.push(NODE(q.x+dx[i],q.y+dy[i],q.bit,q.time+1));
            }
        }
        cout << ans << endl;
    }
}