POJ 1024 Tester Program

[cpp] 
/*
WA
主要思路：
首先DFS建立層次圖。
然後判斷，路徑是否唯一，牆壁是否重復。
*/ 
 
#include <iostream> 
//#define TEST 
using namespace std; 
const int nMax = 105; 
const int mMax = 10100; 
int dis_s[nMax][nMax], dis_e[nMax][nMax]; 
char s[mMax]; 
struct Node 
{ 
    int x1, y1; 
    int x2, y2; 
    Node(){} 
    Node(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){} 
}node[2 * mMax]; 
int ind; 
int visit[nMax][nMax]; 
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; 
int W, H; 
int n; 
int step; 
struct Queue 
{ 
    int x, y; 
    Queue(){} 
    Queue(int x, int y):x(x), y(y){} 
}queue[mMax]; 
 
bool isExist(int a, int b, int x, int y)//判斷(a,b)(x,y)之間是否存在牆 
{ 
    for(int i = 0; i < ind; ++ i) 
    { 
        if(node[i].x1 == a && node[i].y1 == b && node[i].x2 == x && node[i].y2 == y) 
            return 1; 
    } 
    return 0; 
} 
 
void bfs(int a, int b, int dis[][nMax])//建層次圖，原來出錯，BFS，需要用到隊列 
{ 
    int front, rear; 
    front = rear = 0; 
    queue[front ++] = Queue(a, b); 
    while(rear < front) 
    { 
        int x = queue[rear].x; 
        int y = queue[rear].y; 
        rear ++; 
        for(int i = 0; i < 4; ++ i) 
        { 
            int _x = x + dir[i][0]; 
            int _y = y + dir[i][1]; 
            if(_x >= 0 && _x < W && _y >= 0 && _y < H) 
            { 
                if(!isExist(x, y, _x, _y) && dis[_x][_y] == -1) 
                { 
                    dis[_x][_y] = dis[x][y] + 1; 
                    queue[front ++] = Queue(_x, _y); 
                } 
            } 
        } 
    } 
 
} 
 
bool isUnique()//判斷路徑是否唯一 
{ 
    for(int i = 0; i < W; ++ i) 
    { 
        for(int j = 0; j < H; ++ j) 
        { 
            if(!visit[i][j]) 
            { 
                if(dis_s[i][j] + dis_e[i][j] <= step)//空余位置節點到起始點和終點距離之和小於等於step 
                    return 0; 
            } 
        } 
    } 
    return 1; 
} 
 
bool isRepeat() 
{ 
    for(int i = 0; i < n; ++ i) 
    { 
        if(dis_s[node[i].x1][node[i].y1] + dis_e[node[i].x2][node[i].y2] >= step && dis_e[node[i].x1][node[i].y1] + dis_s[node[i].x2][node[i].y2] >= step) 
        //牆壁兩側到起始點和終點的距離之和大於等於step 
            return 1; 
    } 
    return 0; 
} 
 
int main() 
{ 
    freopen("e://data.txt", "r", stdin); 
    //freopen("e://dataout.txt", "w", stdout); 
    int T; 
    scanf("%d", &T); 
    while(T --) 
    { 
        int flag = 0; 
        scanf("%d%d", &H, &W); 
        scanf("%s", s); 
        scanf("%d", &n); 
        int x1, y1, x2, y2; 
        ind = 0; 
        for(int i = 0; i < n; ++ i) 
        { 
            scanf("%d%d%d%d", &y1, &x1, &y2, &x2); 
            node[ind ++] = Node(x1, y1, x2, y2); 
            node[ind ++] = Node(x2, y2, x1, y1); 
        } 
        int a, b; 
        a = b = 0; 
        step = strlen(s); 
        memset(visit, 0, sizeof(visit)); 
        visit[0][0] = 1; 
        for(int i = 0; i < step; ++ i) 
        { 
            int x1, y1; 
            x1 = a; 
            y1 = b; 
            if(s[i] == 'L') 
                b --; 
            else if(s[i] == 'R') 
                b ++; 
            else if(s[i] == 'U') 
                a ++; 
            else if(s[i] == 'D') 
                a --; 
            if(isExist(x1, y1, a, b) || a < 0 || a >= W || b < 0 || b >= H) 
            { 
                flag = 1; 
                break; 
            } 
            visit[a][b] = 1; 
        } 
        if(flag) 
        { 
            printf("INCORRECT\n"); 
            continue; 
        } 
        memset(dis_e, -1, sizeof(dis_e)); 
        dis_e[a][b] = 0; 
        bfs(a, b, dis_e); 
        memset(dis_s, -1, sizeof(dis_s)); 
        dis_s[0][0] = 0; 
        bfs(0, 0, dis_s); 
#ifdef TEST 
        for(int i = 0; i < W; ++ i) 
        { 
            for(int j = 0; j < H; ++ j) 
            { 
                printf("%d\t", dis_s[i][j]); 
            } 
            printf("\n"); 
        } 
        printf("\n\n"); 
        for(int i = 0; i < W; ++ i) 
        { 
            for(int j = 0; j < H; ++ j) 
            { 
                printf("%d\t", dis_e[i][j]); 
            } 
            printf("\n"); 
        } 
#endif 
        bool test1, test2; 
        test1 = isUnique(); 
        test2 = isRepeat(); 
        if(test1 && !test2) 
            printf("CORRECT\n"); 
        else 
            printf("INCORRECT\n"); 
    } 
    return 0; 
} 

作者：lhshaoren