UVA 11487 Gathering Food ( DP 統計路徑數 )

傳出去才覺得dp判斷該不該走的部分怪怪的，不過AC了。之後可能要小心一點，從終點回去比較好。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 2;
const int INF = 0x3f3f3f3f;

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

int n;
char brd[ MAXN ][ MAXN ];
int sx, sy;
int gc, gx, gy;

int dis[ 27 ][ MAXN ][ MAXN ]; // now on where, last alphabet taken

typedef pair< int, int > pii;

bool outOfRange(int x, int y){
    return x < 0 || x >= n || y < 0 || y >= n;
}

const int MOD = 20437;
int way[ 27 ][ MAXN ][ MAXN ];

int dp(int c, int x, int y){
    // if( c == 5 && x == 4 && y == 3 ) puts("HI");
    int &res = way[ c ][ x ][ y ];
    if( ~res ) return res;
    res = 0;
    for(int di = 0; di < 4; ++di){
        int nx = x + dx[ di ];
        int ny = y + dy[ di ];
        if( outOfRange( nx, ny ) ) continue;
        if( brd[ nx ][ ny ] == '.' || brd[ nx ][ ny ] - 'A' + 1 <= c ){
            if( dis[ c ][ nx ][ ny ] - 1 == dis[ c ][ x ][ y ] )
                res = ( res + dp( c, nx, ny ) ) % MOD;
        } else if( brd[ nx ][ ny ] - 'A' + 1 == c + 1 ){
            if( dis[ c + 1 ][ nx ][ ny ] - 1 == dis[ c ][ x ][ y ] )
                res = ( res + dp( c + 1, nx, ny ) ) % MOD;
        }
    }
    return res;
}

void solve(){
    queue< pii > que;
    que.push( pii( 0, 1 * MAXN * MAXN + sx * MAXN + sy ) );
    memset( dis, INF, sizeof(dis) );
    dis[ 1 ][ sx ][ sy ] = 0;
    while( !que.empty() ){
        int w = que.front().first;
        int c = que.front().second / MAXN / MAXN;
        int x = que.front().second / MAXN % MAXN;
        int y = que.front().second % MAXN;
        que.pop();
        for(int di = 0; di < 4; ++di){
            int nx = x + dx[ di ];
            int ny = y + dy[ di ];
            if( outOfRange( nx, ny ) ) continue;
            if( brd[ nx ][ ny ] == '#' ) continue;
            if( brd[ nx ][ ny ] == '.' || brd[ nx ][ ny ] - 'A' + 1 <= c ){
                if( dis[ c ][ nx ][ ny ] > dis[ c ][ x ][ y ] + 1 ){
                    dis[ c ][ nx ][ ny ] = dis[ c ][ x ][ y ] + 1;
                    que.push( pii( w + 1, c * MAXN * MAXN + nx * MAXN + ny ) );
                }
            } else if( brd[ nx ][ ny ] - 'A' + 1 == c + 1 ){
                if( dis[ c + 1 ][ nx ][ ny ] > dis[ c ][ x ][ y ] + 1 ){
                    dis[ c + 1 ][ nx ][ ny ] = dis[ c ][ x ][ y ] + 1;
                    que.push( pii( w + 1, ( c + 1 ) * MAXN * MAXN + nx * MAXN + ny ) );
                }
            }
        }
    }
    if( dis[ gc ][ gx ][ gy ] == INF ) return (void)puts("Impossible");
    memset( way, -1, sizeof(way) );
    way[ gc ][ gx ][ gy ] = 1;
    printf("%d %d\n", dis[ gc ][ gx ][ gy ], dp( 1, sx, sy ));
}

int main(){
    int kase = 0;
    while( scanf("%d", &n) == 1 && n ){
        gc = 0;
        for(int i = 0; i < n; ++i){
            scanf("%s", brd[ i ]);
            for(int j = 0; j < n; ++j){
                if( brd[ i ][ j ] == 'A' )
                    sx = i, sy = j;
                if( brd[ i ][ j ] - 'A' + 1 > gc )
                    gc = brd[ i ][ j ] - 'A' + 1,
                    gx = i, gy = j;
            }
        }
        printf("Case %d: ", ++kase);
        solve();
    }
    return 0;
}