连连看
题目：http://acm.hdu.样例都过了，但是交评测都是Wrong Answer，请各位高手帮我看看到底哪里错了：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int map[1000][1000];
int queue[1000000][4];
int visit[1000][1000];
int min=999999;
int judge(int x,int y,int n,int m,int endx,int endy)
{
if(x>=0&&x<n&&y>=0&&y<m&&(map[x][y]==0||((x==endx&&y==endy))))
return 1;
return 0;
}
int bfs(int n,int m,int startx,int starty,int endx,int endy)
{
int head=0,tail=1;
int i,x,y,dir,xx,yy,step;
queue[0][0]=startx;
queue[0][1]=starty;
queue[0][2]=0;
queue[0][3]=-1;
while(head<tail)
{
x=queue[head][0];
y=queue[head][1];
step=queue[head][2];
dir=queue[head][3];
//printf("%d %d %d\n",x+1,y+1,step);
if(x==endx&&y==endy)
{
if(visit[x][y]<min)
min=visit[x][y];
}
head++;
for(i=0;i<4;i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(judge(xx,yy,n,m,endx,endy)==1&&step<visit[xx][yy])
{
if(dir==-1) //初始化
{
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=0;
queue[tail][3]=i;
visit[xx][yy]=step;
tail++;
continue;
}
else if(dir!=i) //需要转弯
{
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=step+1;
queue[tail][3]=i;
visit[xx][yy]=step+1;
tail++;
continue;
}
else//不需转弯，继续前进
{
queue[tail][0]=xx;
queue[tail][1]=yy;
queue[tail][2]=step;
queue[tail][3]=i;
visit[xx][yy]=step;
tail++;
continue;
}
}
}
}
return 0;
}
int main()
{
int n,m,startx,starty,endx,endy;
int i,j,t;
while(1)
{
scanf("%d %d",&n,&m);
if(n==0&&m==0)
break;
memset(map,0,sizeof(map));
memset(queue,0,sizeof(queue));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
visit[i][j]=999999;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&map[i][j]);
scanf("%d",&t);
for(i=0;i<t;i++)
{
min=999999;
scanf("%d %d",&startx,&starty);
scanf("%d %d",&endx,&endy);
startx--,starty--;
endx--,endy--;
if(map[startx][starty]!=map[endx][endy])
{
printf("NO\n");
continue;
}
if(map[startx][starty]==0||map[endx][endy]==0||(startx==endx&&starty==endy))
{
printf("NO\n");
continue;
}
bfs(n,m,startx,starty,endx,endy);
//printf("%d\n",min);
if(min<=2)
printf("YES\n");
else
printf("NO\n");
}
}
system("pause");
return 0;
}
[ 本帖最后由 sunyh1999 于 2011-5-28 20:06 编辑 ]
