AOJ 0245: Time Sale

全探索だと状態が爆発しちゃうので, メモ化できるところはメモ化してしまいたい問題です.
どの状態を保持するかを見極められるのが大切ですね. これできれば誰も苦労しないか...
Q & Aに「その場で立ち止まるのも良い」と書かれていたので零ベクトルを移動に追加しましたが,
立ち止まるのが最適な場面ってどんな場面でしょう.セールス待ちかな.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

bool v[1024][20][20][101];
char map[20][21];

typedef struct {
    int tx, ty;
    int bit;
    int time;
    int score;
} Move;

int main(void)
{
    int x, y;
    int ans;
    int n;
    int idx, plus[10], s[10], e[10];
    int dx[] = {1, 0, -1, 0, 0};
    int dy[] = {0, 1, 0, -1, 0};
    Move st;
    
    while (scanf("%d %d", &x, &y) && x){
        for (int i = 0; i < y; i++){
            for (int j = 0; j < x; j++){
                cin >> map[i][j];
                if (map[i][j] == '.'){
                    map[i][j] = -1;
                }
                else if (map[i][j] == 'P'){
                    map[i][j] = -1;
                    st.ty = i;
                    st.tx = j;
                }
                else {
                    map[i][j] -= '0';
                }
            }
        }
        
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++){
            scanf("%d", &idx);
            scanf("%d %d %d", &plus[idx], &s[idx], &e[idx]);
        }
        
        memset(v, 0, sizeof(v));
        st.time = st.score = st.bit = 0;
        ans = 0;
        
        queue<Move> que;
        
        v[0][st.ty][st.tx][0] = true;
        
        que.push(st);
        
        while (!que.empty()){
            Move temp = que.front();
            que.pop();
            if (temp.time > 100){
                break;
            }
            
            for (int i = 0; i < 4; i++){
                int mx = temp.tx + dx[i], my = temp.ty + dy[i];
                if (0 <= mx && mx < x && 0 <= my && my < y && ~map[my][mx]
                        && s[map[my][mx]] <= temp.time && temp.time < e[map[my][mx]]){
                    if (!((temp.bit >> map[my][mx]) & 1)){
                        temp.score += plus[map[my][mx]];
                    }
                    temp.bit |= (1 << map[my][mx]);
    
                }
            }
            
            ans = max(ans, temp.score);
            
            for (int i = 0; i < 5; i++){
                int mx = temp.tx + dx[i], my = temp.ty + dy[i];
                if (0 <= mx && mx < x && 0 <= my && my < y){
                    if (map[my][mx] == -1 && v[temp.bit][my][mx][temp.time + 1] == false){
                        st = temp;
                        st.time++;
                        st.tx = mx, st.ty = my;
                        v[st.bit][st.ty][st.tx][st.time] = true;
                        que.push(st);
                    }
                }
            }
        }
        
        printf("%d\n", ans);
    }
        
    return (0);
}