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;
}
```