poj 1024（bfs的扩展，最短路径不唯一的判定，围墙围住封闭空间的判定）

#include
#include
using namespace std;
#define maxn 105
int m,n,w_num,path_num;
typedef struct node{
    int x1,y1,x2,y2;
}Wall;
Wall wall[maxn*maxn];
int dis_s[maxn][maxn],dis_e[maxn][maxn];
void bfs(int x1,int y1,int dis[][maxn]){
    bool vis_bfs[maxn][maxn] = {false},isgo;
    int dx[] = {0,1,0,-1};
    int dy[] = {1,0,-1,0};
    vis_bfs[x1][y1] = true;
    int head = 0,tail = 0;
    int Qx[maxn*maxn],Qy[maxn*maxn];
    Qx[tail] = x1;Qy[tail] = y1;tail++; 
    while(head<tail){
        int x = Qx[head];
        int y = Qy[head];
        head++;
        for(int i=0;i<4;i++){
            int px = x+dx[i];
            int py = y+dy[i];
            if(vis_bfs[px][py]||px<0||py<0||px>=m||py>=n){
                continue;
            }
            isgo = true;
            for(int j=0;j){
                int x1 = wall[j].x1,y1 = wall[j].y1;
                int x2 = wall[j].x2,y2 = wall[j].y2;
                if((px==x1&&py==y1&&x==x2&&y==y2)
                 ||(px==x2&&py==y2&&x==x1&&y==y1)){
                     isgo = false;
                     break;
                }
            }
            if(!isgo)continue;
            dis[px][py] = dis[x][y]+1;
            vis_bfs[px][py] = true;
            Qx[tail] = px;
            Qy[tail] = py;
            tail++;            
        }
    }
}
int main(){
    int cnt,endx,endy;
    char c;
    bool fail,vis[maxn][maxn];
    scanf("%d",&cnt);
    while(cnt--){
        path_num = endx = endy = 0;
        memset(vis,false,sizeof(vis));
        vis[0][0] = true;
        scanf("%d%d\n",&m,&n);
        while(c=getchar(),c!='\n'){
            switch(c){
                case 'R':endx++;break;
                case 'L':endx--;break;
                case 'U':endy++;break;
                case 'D':endy--;break;
            }
            path_num++;
            vis[endx][endy] = true;
        }
        scanf("%d",&w_num);
        for(int i=0;i){
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            wall[i].x1 = x1;
            wall[i].y1 = y1;
            wall[i].x2 = x2;
            wall[i].y2 = y2;
        }
        memset(dis_s,0,sizeof(dis_s));
        memset(dis_e,0,sizeof(dis_e));
        bfs(0,0,dis_s);
        bfs(endx,endy,dis_e);
//        cout<//        for(int j=n-1;j>-1;j--){
//            for(int i=0;i//                printf("%3d",dis_e[i][j]); 
//            }
//            cout<//        }
//        cout<
        fail = false;
        for(int i=0;i){
            for(int j=0;j){
                if(!vis[i][j]&&dis_s[i][j]+dis_e[i][j]==path_num){
                    fail = true;
                    break;
                }
            }
            if(fail)break;
        } 
        if(fail){
            printf("INCORRECT\n");
            continue;
        }
        fail = false;
        for(int i=0;i){
            int x1 = wall[i].x1;
            int y1 = wall[i].y1;
            int x2 = wall[i].x2;
            int y2 = wall[i].y2;
            if((dis_s[x1][y1]+dis_e[x2][y2]>path_num
              &&dis_s[x2][y2]+dis_e[x1][y1]>path_num)
             ||(dis_s[x1][y1]==0&&dis_e[x1][y1]==0)
             ||(dis_s[x2][y2]==0&&dis_e[x2][y2]==0)){
                fail = true;
                break;
            }
        }
        if(fail){
            printf("INCORRECT\n");
            continue;
        }
        printf("CORRECT\n");
    }
    return 0;
}