POJ 1024 Tester Program(DFS求单源最短路径)

POJ 1024 Tester Program(DFS求单源最短路径)

http://poj.org/problem?id=1024

题意:现在有一个迷宫,我们给出一条最短路径,然后继续给出这个迷宫的墙的构造方式,要你检查最短路径是否唯一 且 这些墙是不是有多余?

分析:仔细体会如何用DFS一次求出单源最短距离.

首先我们根据上面给的最短路径和墙的信息构图(具体看代码,仔细体会),然后

1.用DFS()求源点到所有点的最短距离

2.用DFS()求终点到所有点的最短距离

3.如果该点不在最短路径上,那么它到源点的距离+ 它到终点的距离

> min_path 最短距离. 否则最短路径不唯一.

4. 如果相邻两点有墙,那么点i到源点的距离 +1 + 点j到终点的距离 <= min_path 或点i到终点的距离 +1 +点j到源点的距离 <=min_path . 否则墙多余.

5. 如果某个点被墙包围了,可以证明墙也肯定至少多余1块.(可以分析一下),在代码中由于默认len[0]=len[1]=0,所以如果某个点被包围了,那么它的len[0]+len[1]=0 小于min_path,所以肯定会被检测到.

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100+5;
struct Node
{
    int len[2];     //len[0]表示该点到源点的最短距离,len[1]表示该点到终点的最短距离
    bool used;      //该点是否在所给的最短路径上
    bool r,u;       //r=true表示该点的右边有墙,u表示该点的上面有墙
}p[maxn][maxn];     //p的第一维是x坐标,第二维是y坐标
//P读完输入后,整个图的信息就全保存在p中了.(除了图的高和宽,还有最短路径长)
int width,height;
int min_path;//最短路径长
int dx,dy;//终点坐标

void dfs(int x,int y,int len,int flag)//len是当前走的长度,flag=0表示从源点出发,flag=1表从终点出发
{
    if(len>=p[x][y].len[flag] && p[x][y].len[flag]!=0)//距离太长,不用再走下去了
        return ;
    if(x+y!=0 && (x!=dx || y!= dy) )     //当前点不是起点或终点
        p[x][y].len[flag]=len;
    if(x+1<width && p[x][y].r==false )   //右边可走
        dfs(x+1,y,len+1,flag);
    if(x-1>=0 && p[x-1][y].r==false)      //左边可走
        dfs(x-1,y,len+1,flag);
    if(y+1<height && p[x][y].u==false)  //上面可走
        dfs(x,y+1,len+1,flag);
    if(y-1>=0 && p[x][y-1].u==false)      //下面可走
        dfs(x,y-1,len+1,flag);
}
bool judge()
{
    for(int x=0;x<width;x++)
    for(int y=0;y<height;y++)
    {
        if(p[x][y].used==false && p[x][y].len[0] + p[x][y].len[1]<= min_path)//最短路不唯一或者有某个点被墙包围了
            return false;
        if(p[x][y].r==true && x+1<width && p[x][y].len[0]+1+p[x+1][y].len[1]> min_path && p[x][y].len[1]+1+p[x+1][y].len[0]>min_path)//墙多余
            return false;
        if(p[x][y].u==true && y+1<height && p[x][y].len[0]+1+p[x][y+1].len[1]> min_path && p[x][y].len[1]+1+p[x][y+1].len[0]>min_path)//墙多余
            return false;
    }
    return true;
}
int main()
{
    int T;
    int x1,y1,x2,y2;
    char path[400];//其实应该是10000
    scanf("%d",&T);
    while(T--)
    {
        memset(p,0,sizeof(p));
        scanf("%d%d",&width,&height);
        scanf("%s",path);
        min_path=dx=dy=0;
        p[0][0].used=true;
        for(int i=0;path[i];i++)
        {
            if(path[i]=='R')      dx++;
            else if(path[i]=='L') dx--;
            else if(path[i]=='U') dy++;
            else if(path[i]=='D') dy--;
            p[dx][dy].used=true;
            min_path++;
        }
        int wall_num;
        scanf("%d",&wall_num);
        while(wall_num--)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int x=x1-x2,y=y1-y2;
            if(x==0 && y==1) p[x2][y2].u=true;
            else if(x==0 && y==-1) p[x1][y1].u=true;
            else if(x==1 && y==0) p[x2][y2].r=true;
            else if(x==-1 && y==0) p[x1][y1].r=true;
        }
        dfs(0,0,0,0);
        dfs(dx,dy,0,1);
        if(judge()) printf("CORRECT\n");
        else printf("INCORRECT\n");
    }
    return 0;
}