Question

杭电 acm 1175 测试数据都过为什么一直都是wa 求解

#include<stdio.h>

#include<string.h>
int a[1010][1010];
int heng[4]={1,0,-1,0};
int shu[4]={0,1,0,-1};
int n,m;
int judge=0;
int find(int x1,int y1,int x2,int y2)
{
int i;
if(judge==1)
return 1;
for(i=0;i<4;i++)
{
a[x1][y1]=1;
if((x1+heng[i])==x2&&(y1+shu[i])==y2)
{
judge=1;
return 1;
}
if((0<=(x1+heng[i]))&&((x1+heng[i])<n)&&(0<=y1+shu[i])&&(y1+shu[i]<m)&&a[x1+heng[i]][y1+shu[i]]==0)
{
x1=x1+heng[i];
y1=y1+shu[i];
find(x1,y1,x2,y2);
a[x1][y1]=0;
x1=x1-heng[i];
y1=y1-shu[i];
}
}
if(x1==0&&y1==0&&judge==0)
return 0;
}
void check(int x1,int y1,int x2,int y2)
{
if(a[x1][y1]!=a[x2][y2])
{
printf("NO\n");
}
else
{
if((a[x1][y1]==0)||(a[x2][y2]==0)||(a[x1][y1]==-1)||(a[x2][y2]==-1))
{
printf("NO\n");
}
else
{
if(find(x1,y1,x2,y2))
{
printf("YES\n");
return;
}
else
printf("NO\n");
}
}

}
int main()
{
int t,i,j,x1,y1,x2,y2;
memset(a,-1,sizeof(a));
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
}
}
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
check(x1-1,y1-1,x2-1,y2-1);
}
}
return 0;
}
题目 http://acm.hdu.edu.cn/showproblem.php?pid=1175

Answer 1

原题目已经说了，线的转折次数不能超过2，你的代码里面没有体现，然后你的全局变量judge不知道用来干什么的 0.0，在你的代码基础上，重新写了find函数，增加了两个参数left，就是剩余的转弯次数，还有last，上次的方向（方向要么打横，要么打竖）用的是DFS，我提交的时候是可以过的，不会超时，只是……每次提交用的时间越来越多而已……

#include<string.h>
#include<stdio.h>
int a[1010][1010];
int heng[4]={1,0,-1,0};
int shu[4]={0,1,0,-1};
int n,m;
int judge=0;

int findx(int x1, int y1, int x2, int y2, int left, int last)
{
    int i;
    for (i = 0;i < 4;i++)
    {
        int cx = x1 + heng[i];
        int cy = y1 + shu[i];
        if ( 0 <= cx && cx < n && cy < m && 0 <= cy )
        {
            int t = i % 2;
            if (cx == x2 && cy == y2 && (left || t == last))
                return 1;
            if (a[cx][cy] == 0)
            {
                a[cx][cy] = -1;
                if (t != last && left && findx(cx, cy, x2, y2, left - 1, t))
                {
                    a[cx][cy] = 0;
                    return 1;
                }
                if (t == last && findx(cx, cy, x2, y2, left, t))
                {
                    a[cx][cy] = 0;
                    return 1;
                }
                a[cx][cy] = 0;
            }
        }
    }
    return 0;
}

void check(int x1,int y1,int x2,int y2)
{
    if(a[x1][y1]!=a[x2][y2] || !a[x1][y1])
    {
        printf("NO\n");
    }
    else
    {
        if(findx(x1,y1,x2,y2, 3, -1))
        {
            printf("YES\n");
            return;
        }
        else
            printf("NO\n");
    }
}

int main()
{
    int t,i,j,x1,y1,x2,y2;
    memset(a,-1,sizeof(a));
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {
        for(i=0;i<n;i++)
        {
           for(j=0;j<m;j++)
           {
               scanf("%d",&a[i][j]);
           }
        }
        scanf("%d",&t);
        for(i=0;i<t;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            check(x1-1,y1-1,x2-1,y2-1);
        }
    }
    return 0;
}

追问

好的 。。。至少我知道我哪里错了 我的judge是检测到一条可以的路径就不在寻求第二条路径了 知道哪里错了就好。。谢谢大神指导

追答

0.0 you are welcome