AOJ 2419 Acrophobia

Cheeseに似てる問題。
巻物が高々5個しかないのでcost[100][100][1<<5]で全て持つ事ができる。
基本的にはBFSしていけばいいがコストが均一でないので初めに見つけたものが最適では
ない可能性があるので、現在よりもよいコストで行けるのが見つかったらそこからまた
探索していけばよい。

Dijkstra

以下コード

#include <iostream>
#include <deque>
#include <cstring>
#include <algorithm>

using namespace std;

int visited[102][102][1<<5];
int co[102][102];
char f[102][102];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

class state{
    public:
    int x,y,co,st;
    
    state(){}    
    state(int _y, int _x, int _co, int _state){
        x = _x;
        y = _y;
        co = _co;
        st = _state;
    }
};

int main(){
    int w,h;
    int sx, sy, gx, gy;
    int m=0;
    memset(co, -1 , sizeof(co));
    fill((int *)visited, (int *)visited+102*102*(1<<5), 1 << 29);
    cin >> w >> h;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            co[i][j] = 1;
        }
    }
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin >> f[i][j];
            if(f[i][j] == '#'){
                for(int p=-2;p<=2;p++){
                    for(int q=-2;q<=2;q++){
                        if(0 <= i+p && i+p <= h && 0 <= j+q && j+q <= w){
                            if((p == 0 && q == 0) || co[i+p][j+q] == -1){
                                co[i+p][j+q] = -1;
                            }else if(max(abs(p), abs(q)) == 2){
                                co[i+p][j+q] = max(co[i+p][j+q],2);
                            }else{
                                co[i+p][j+q] = max(co[i+p][j+q],3);
                            }
                        }
                    }
                }
            }else if(f[i][j] == 'S'){
                sy = i;
                sx = j;
            }else if(f[i][j] == 'G'){
                gy = i;
                gx = j;
            }else if(f[i][j] == 'M'){
                f[i][j] = m + '0';
                m++;
            }
        }
    }
    deque<state> q;
    state st;
    int tx,ty,tco,tstate,nx,ny,nstate;
    q.push_back(state(sy,sx,0,0));
    visited[sy][sx][0] = 0;
    while(!q.empty()){
        st = q.front();
        q.pop_front();
        tx = st.x;
        ty = st.y;
        tco = st.co;
        tstate = st.st;
        for(int i=0;i<4;i++){
            nx = tx + dx[i];
            ny = ty + dy[i];
            if(co[ny][nx] == -1) continue;
            if('0' <= f[ny][nx] && f[ny][nx] <= '9'){
                nstate = tstate | (1 << (f[ny][nx] - '0'));
                if(visited[ny][nx][nstate] > tco + co[ty][tx]){
                    visited[ny][nx][nstate] = tco + co[ty][tx];
                    q.push_back(state(ny,nx,tco+co[ty][tx],nstate));
                }
            }else{
                if(visited[ny][nx][tstate] > tco + co[ty][tx]){
                    visited[ny][nx][tstate] = tco + co[ty][tx];
                    q.push_back(state(ny,nx,tco+co[ty][tx],tstate));
                }
            }
        }
    }
    cout << visited[gy][gx][(1 << m) - 1] << endl;
}