zoj 1479 Dweep

#include <stdio.h>#include <ctype.h>#include <string.h>#include <map>#include <functional>#include <algorithm>#include <queue>using namespace std;inline bool get(int &t){    bool flag = 0 ;    char c;    while(!isdigit(c = getchar())&&c!='-') if( c == -1 ) break ;    if( c == -1 ) return 0 ;    if(c=='-') flag = 1 , t = 0 ;    else t = c ^ 48;    while(isdigit(c = getchar()))    t = (t << 1) + (t << 3) + (c ^ 48) ;    if(flag) t = -t ;    return 1 ;}typedef pair<int,int> pii ;const int INF = 0x1fffffff ;const int maxn = 22 ;int n , m , sx , sy , ex , ey , border[maxn][maxn] , dist[maxn][maxn] , rep[128] ;char dir[maxn][maxn] ;bool vis[maxn][maxn] ;const int cx[] = {1,0,0,-1} ;const int cy[] = {0,1,-1,0} ;const int ccx[] = {-1,-1,-1,0,0,1,1,1};const int ccy[] = {-1,0,1,-1,1,-1,0,1};inline void init()    //set laser{    int i , j , k , x , y ;    for( i = 1 ; i <= n ; i++)        for( j = 1 ; j <= m ; j++) dist[i][j] = INF ;    dist[sx][sy] = 0 ;    for( i = 1 ; i <= n ; i++)    {        for( j = 1 ; j <= m ; j++) if( border[i][j] == 1 && dir[i][j] != -1 )        { k = dir[i][j] ; x = i + cx[k] ;    y = j + cy[k] ;  border[i][j] = 2 ;while ( x >= 1 && x <= n && y >= 1 && y <= m && border[x][y] != 2 ) {     border[x][y] = 1 ;     x += cx[k] ;     y += cy[k] ; }        }    }}inline void solve(){    init();    queue<pii> q ;    q.push(make_pair(sx,sy));    memset(vis,0,sizeof(vis));    vis[sx][sy] = 1 ;    while(!q.empty())    {        int i , j , k , x , y , nx , ny ;        x = q.front().first ;    y = q.front().second ;        vis[x][y] = 0 ;        q.pop();        if( border[x][y] == 0 )        { for( k = 0 ; k < 8 ; k++) {     nx = x + ccx[k] ;     ny = y + ccy[k] ;     if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m )     {         if( border[nx][ny] == 0 && dist[nx][ny] > dist[x][y] )         {  dist[nx][ny] = dist[x][y] ;  if(!vis[nx][ny])    q.push(make_pair(nx,ny)),vis[nx][ny]=1;         }         else if( border[nx][ny] == 1 && dist[nx][ny] > dist[x][y] + 1 )         {  dist[nx][ny] = dist[x][y] + 1 ;  if(!vis[nx][ny])    q.push(make_pair(nx,ny)),vis[nx][ny]=1;         }     } }        }        else        { for( k = 0 ; k < 8 ; k++) {     nx = x + ccx[k] ;     ny = y + ccy[k] ;     if ( nx >= 1 && nx <= n && ny >= 1 && ny <= m && border[nx][ny] == 0 && dist[nx][ny] > dist[x][y] )     {         dist[nx][ny] = dist[x][y] ;         if(!vis[nx][ny])    q.push(make_pair(nx,ny)),vis[nx][ny]=1;     } }        }    }    printf("%dn",dist[ex][ey]==INF?-1:dist[ex][ey]);}int main(){    int i , x , y , j , k ;    char op[10];    rep['d'] = 0 ;    rep['l'] = 2 ;    rep['u'] = 3 ;    rep['r'] = 1 ;    while (get(n))    {        get(m);        get(sx); get(sy); get(ex); get(ey);        get(k);        memset(border,0,sizeof(border));        for( i = 0 ; i < maxn ; i++)for( j = 0 ; j < maxn ; j++)dir[i][j] = -1 ;        while(k--)        { get(x);    get(y); scanf("%s",op); if( op[0] != 'B' )  {     dir[x][y] = rep[op[0]] ;     border[x][y] = 1 ; } else border[x][y] = 2 ;}        solve();    }}