当前位置:编程学习 > C/C++ >>

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') 
              
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,