传送门
题意
给定一个n*m的矩阵，询问q次，两个方块是否能被消掉，弯折次数不超过两次
分析
这题写了有一个下午，思路很简单，但是有很多trick，（唉），我还是太弱
trick
初始判断：1.两点不重叠
2.两点数值相等并且不为空
dfs中判断：1.每次访问节点深搜时打访问标记，回溯取消标记
2.一个强力剪枝 if(cnt==2&&(x-x2)&&(y-y2)) return ;
讲解：如果当到达一点弯折度已达2，并且该点与终点不在同一行/列，则返回。
强力剪枝！将我交的第一发8517ms降到124ms，很强！
代码
#include<cstdio>
#include<cstring>
#define R(i,a,b) for(int i=a;i<b;++i)
#define F(i,a,b) for(int i=a;i<=b;++i)
#define mem(a,b) memset(a,b,sizeof(a))
int t,n,m,a[1010][1010],q,x1,y1,x2,y2;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int flag;
void dfs(int x,int y,int cnt,int pre)
{
// printf("1.x=%d y=%d cnt=%d pre=%d\n",x,y,cnt,pre);
if(flag) return ;
if(x<1||y<1||x>n||y>m) return ;
if(cnt>2) return ;
if(cnt==2&&(x-x2)&&(y-y2)) return ;
//printf("(cnt==2&&(x-x2)&&(y-y2))=%d\n",(cnt==2&&(x-x2)&&(y-y2)));
//if(cnt==2&&(x-x2)&&(y-y2)) return ;
if(x2==x&&y2==y) { flag=1;return ; }
//printf("a[%d][%d]=%d\n",x,y,a[x][y]);
//printf("2.x=%d y=%d cnt=%d pre=%d\n",x,y,cnt,pre);
R(i,0,4)
{
int xx=x+dir[i][0],yy=y+dir[i][1];
int cnt1;
if(pre!=i) cnt1=cnt+1;else cnt1=cnt;
if(a[xx][yy]==0)
{
a[xx][yy]=1;
//printf("3.a[%d][%d]=%d\n",xx,yy,a[xx][yy]);
dfs(xx,yy,cnt1,i);
a[xx][yy]=0;
}
else if(xx==x2&&yy==y2)
{
dfs(xx,yy,cnt1,i);
if(flag) return ;
}
// printf("3.x=%d y=%d cnt=%d pre=%d\n",xx,yy,cnt,pre);
//if(pre!=i) dfs(xx,yy,cnt+1,i);else dfs(xx,yy,cnt,i);
}
}
int main()
{
while(scanf("%d %d",&n,&m),n+m)
{
F(i,1,n)F(j,1,m) scanf("%d",&a[i][j]);
for(scanf("%d",&q);q--;)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
if(a[x1][y1]!=a[x2][y2]||a[x1][y1]==0||(x1==x2&&y1==y2)) { flag=0;goto l; }
flag=0;
R(i,0,4)
{
int xx=x1+dir[i][0],yy=y1+dir[i][1];
if(xx<1||yy<1||xx>n||yy>m) continue;
if(flag) break;
if(a[xx][yy]==0)
{
a[xx][yy]=1;//已访问过
dfs(xx,yy,0,i);
a[xx][yy]=0;//回溯清标记
}
else if(xx==x2&&yy==y2)
{
dfs(xx,yy,0,i);
}
}
l:if(flag) puts("YES");else puts("NO");
}
}
}