p3346.cpp

来自「大概POJ上50道比较难的题的代码」· C++ 代码 · 共 87 行

#include <iostream>
#include <string>
using namespace std;
const int MAXN = 110;
const int MAX_INT = 100000000;
const int move[4][2] = {-1,0,1,0,0,-1,0,1};
int f,c,n,m;
string s[MAXN];
int vi[30][MAXN][MAXN];
int l[MAXN*MAXN*30][4];
void enter(int x,int y){
    if(s[x][y] == '#' || s[x][y] >= 'A' && s[x][y] <= 'Z'){
        l[c][0] = x;
        l[c][1] = y;
        l[c][3] = 0;
        if(s[x][y] == '#') l[c][2] = 0;
        else l[c][2] = s[x][y] - 'A' + 1;
        ++c;
    }
}
inline bool ok(int x,int y){
    return (x > 0 && x < n-1 && y > 0 && y < m-1 && s[x][y] != '*');
}
int main(){
    n = 0;
    getline(cin ,s[0]);
    while(s[0] != "--"){
        f = c = 0;
        m = s[0].size();
        for(int i = 0;i < m;++i) enter(0,i);
        getline(cin,s[++n]);
        while(s[n] != ""){
            enter(n,0); enter(n,m-1);
            getline(cin,s[++n]);
        }
        for(int i = 0;i < m;++i) enter(n-1,i);
        for(int k = 0;k <= 26;++k)
            for(int i = 0;i < n;++i)
                for(int j = 0;j < m;++j) vi[k][i][j] = MAX_INT;        
        --c;
//        puts("init done");
        int ans(MAX_INT);
//        for(int i = 0;i <= c;++i) printf("x=%d y=%d d=%d st=%d\n",l[i][0],l[i][1],l[i][2],l[i][3]);
        while(f <= c && c < MAXN*MAXN*30){
            int x(l[f][0]),y(l[f][1]),d(l[f][2]),st(l[f][3]);
//            printf("fa  x=%d y=%d d=%d st=%d\n",x,y,d,st);
//            if(x == 1 && y == 2){ cout << y << " " << d << " " << st << endl; system("pause");}            
            for(int i = 0;i < 4;++i){
//                printf("x=%d y=%d d=%d st=%d",x,y,d,st); system("pause");
                x += move[i][0];    y += move[i][1];
//                printf("x=%d y=%d\n",x,y);  system("pause");
                if(ok(x,y)){
//                    printf("%d %d %d %d\n",d,x,y,vi[d][x][y]);                    
                    if(s[x][y] == '$') ans = min(ans,st);
                    if(s[x][y] >= '1' && s[x][y] <= '9'){
                      if(d > 0 && vi[d-1][x][y] > st){
                        ++c;
                        l[c][0] = x; l[c][1] = y;
                        l[c][2] = d - 1; l[c][3] = st;
                        vi[d-1][x][y] = st;
//                        printf("x=%d y=%d d=%d\n",x,y,d-1); 
                      }
                      if(vi[d][x][y] > st + s[x][y] - '0'){
                        ++c;
                        l[c][0] = x; l[c][1] = y;
                        l[c][2] = d; l[c][3] = st + s[x][y] - '0';
                        vi[d][x][y] = st + s[x][y] - '0';
//                        printf("x=%d y=%d d=%d\n",x,y,d);                        
                      }
                    }
                    if(s[x][y] == '.' && vi[d][x][y] > st){
                        ++c;
                        l[c][0] = x; l[c][1] = y;
                        l[c][2] = d; l[c][3] = st;
                        vi[d][x][y] = st;
                    }
                }
                x -= move[i][0];    y -= move[i][1];
            }
            ++f;
        }
        if(ans == MAX_INT) puts("IMPOSSIBLE");
        else cout << ans << endl;
        n = 0;
        getline(cin,s[0]);
    }
}