CFR 129 C. Statues ( BFS )

Problem - C - Codeforces
WA了一次，以為只會原地待著，或往上或往右或往右上移動。仔細想想，這全部方向都得考慮。

#include <bits/stdc++.h>
using namespace std;
const int MAXH = 8 + 2;
const int MAXW = 8 + 2;
typedef pair< int, int > pii;

char G[ MAXH ][ MAXW ];
int has_stat[ MAXH ][ MAXH ][ MAXW ];

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

int vis[ 2 * MAXH ][ MAXH ][ MAXW ];

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

void solve(){
    for( int i = 0; i < 8; ++i )
        for( int j = 0; j < 8; ++j )
            if( G[ i ][ j ] == 'S' )
                for( int k = 0; i + k < 8; ++k )
                    has_stat[ k ][ i + k ][ j ] = 1;
    /*for( int i = 0; i < 8; ++i ) for( int j = 0; j < 8; ++j )
        for( int k = 0; k < 8; ++k ) if( has_stat[ i ][ j ][ k ] ) printf("*%d %d %d\n", i, j, k);*/
    queue< pii > que;
    que.push( pii( 0, 7 * MAXW + 0 ) );
    vis[ 0 ][ 7 ][ 0 ] = 1;
    while( !que.empty() ){
        int t = que.front().first;
        int x = que.front().second / MAXW;
        int y = que.front().second % MAXW;
        // printf("%d %d %d\n", t, x, y);
        que.pop();
        if( x == 0 && y == 7 ) return (void)puts("WIN");
        for( int di = 0; di < 9; ++di ){
            int nx = x + dx[ di ];
            int ny = y + dy[ di ];
            if( outOfRange( nx, ny ) ) continue;
            if( has_stat[ t ][ nx ][ ny ] || has_stat[ t + 1 ][ nx ][ ny ] ) continue;
            if( vis[ t + 1 ][ nx ][ ny ] ) continue;
            vis[ t + 1 ][ nx ][ ny ] = 1;
            que.push( pii( t + 1, nx * MAXW + ny ) );
        }
    }
    puts("LOSE");
}

int main(){
    for( int i = 0; i < 8; ++i )
        scanf("%s", G[ i ]);
    solve();
    return 0;
}