acm 1175 搜索问题——连连看
pid：http://acm.hdu.edu.cn/showproblem.php?pid=1175
第一次提交提示超时。剪枝处理后，现在提示wa。
求一组错误的用例吧。
哎，搜索的题目，ac总是很费力！
//////////////////////////////////////////////////////////////////////////
// 1 2 3 4 5
// 0 0 0 0 0
// 1 0 2 0 0
// 0 0 2 0 0
// 1 0 1 0 0
// eg:1 1 3 1;3 1 5 3
// 1 0 3
// 0 0 4
// 1 0 1
//1 1 3 3
//
#include <iostream>
#include <string.h>
#include <queue>
#define MaxRow 1000
#define MaxCol 1000
#define MaxTurns 2
using namespace std;
typedef struct
{
int xPos;
int yPos;
int flag;//0,1,2,3分别表示上左右下便是从上个位置到这个位置的方向，-1表示起始元素
int turns;//转弯次数
}Postion;
int map[MaxRow][MaxCol];//记录棋盘数据
int direction[4][4]={{-1,0},{0,-1},{0,1},{1,0}};//上左右下
bool CheckFunction(int x1,int y1,int x2,int y2)//x1,y1起始坐标 x2,y2目的坐标
{
queue<Postion> q;
Postion start,popElem,pushElem;
int i,j,x,y,dir,turns,bigx,bigy,smallx,smally;
start.xPos=x1;
start.yPos=y1;
start.flag=-1;
start.turns=0;
if (map[x1][y1]!=map[x2][y2]||map[x1][y1]==0||map[x2][y2]==0||(x1==x2&&y1==y2))//若元素不一样；有0；同一个元素
{
return false;
}
while (!q.empty())
{
q.pop();
}
q.push(start);
while (!q.empty())
{
popElem=q.front();
q.pop();
for (i=0;i<4;i++)
{
if(popElem.flag==3-i)//确保入队元素不回头
{
continue;
}
x=popElem.xPos+direction[i][0];
y=popElem.yPos+direction[i][1];
dir=i;
if (popElem.flag==-1)//若为start元素
{
turns=0;
}
else
{
if (popElem.flag==dir)//同向转弯数目不变
{
turns=popElem.turns;
}
else//否则转弯数目加1
{
turns=popElem.turns+1;
}
}
if (map[x][y]==-1)//出边界
{
continue;
}
else
{
if (x==x2&&y==y2)//找到
{
return true;
}
if (map[x][y]==0 )
{
if (turns==MaxTurns)//剪枝，若已经达到最大转弯数目
{
if (!(x==x2||y==y2))//非同行同列
{
continue;
}
else
{
bigx=x>=x2?x:x2;
smallx=x<x2?x:x2;
bigy=y>=y2?y:y2;
smally=y<y2?y:y2;
if (x==x2)//同行
{
for (j=smally;j<bigy;j++)
{
if (map[x][j]!=0)
{
continue;
}
}
return true;
}
else//同列
{
for (j=smallx;j<bigx;j++)
{
if (map[j][y]!=0)
{
continue;
}
}
return true;
}
}
}
else
{
pushElem.xPos=x;
pushElem.yPos=y;
pushElem.flag=dir;
pushElem.turns=turns;
q.push(pushElem);
}
}
}//end else
}//end for
}//end while
return false;
}//end function
void main()
{
int row,col;
int i,j,n;
int x1,y1,x2,y2;
while (scanf(" %d%d",&row,&col),row||col)
{
memset(map,0,sizeof(map));//清理棋盘
for (i=0;i<=row+1;i++)
{
for (j=0;j<=col+1;j++)
{
if (i==0||j==0||i==row+1||j==col+1)
{
map[i][j]=-1;
}
else
{
scanf(" %d",&map[i][j]);
}
}
}
//
scanf(" %d",&n);
for (i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if (CheckFunction(x1,y1,x2,y2))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
}
