连连看 DFS

忘是亡心i 2024-02-18 23:12 39阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h2>连连看</h2> Time Limit: 20000/10000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 41660&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 10314 &nbsp; Problem Description “连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。 玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。 &nbsp; &nbsp; Input 输入数据有多组。每组数据的第一行有两个正整数n,m(0&lt;n&lt;=1000,0&lt;m&lt;1000)，分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0&lt;q&lt;50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。 注意：询问之间无先后关系，都是针对当前状态的！ &nbsp; &nbsp; Output 每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。 &nbsp; &nbsp; Sample Input <pre>&nbsp;</pre> 3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0 &nbsp; &nbsp; Sample Output <pre>&nbsp;</pre> YES NO NO NO NO YES &nbsp; &nbsp; Author lwg &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

心中有点小疑惑，他的内存是怎么算的，？为什么一开始一直超内存，

下图的代码9860ms险过

<table> 
 <tbody> 
 <tr> 
 <td> <pre>#include&lt;iostream&gt;
#include&lt;algorithm&gt;
#include&lt;string.h&gt; 
using namespace std;
#pragma comment(linker, “/STACK: 1024000000,1024000000 ”) 手动加栈
struct node
{
 
 int x,y;
};
node s,e,ss;
int n,m,f=0,z=0,a[1001][1001],dir[4][2]={
 {
 1,0},{
 0,1},{-1,0},{
 0,-1}};
bool vis[1001][1001];
bool isvalid(node d) 判断你是否在圈内
{
 
 if(d.x&gt;n||d.x&lt;1||d.y&lt;1||d.y&gt;m)
 return false;
 return true;
}
void DFS(node k,node dr,int d) k表示当前探索的坐标节点，dr表示当前的方向节点，d表示有几次转折
{
 
 vis[k.x][k.y]=true;
 if(d&gt;3||f) 这点d应大于3，因为他把从起点到起点到下一个遍历点也算成一次转折
 return ;
 if(k.x==e.x&amp;&amp;k.y==e.y) 
 {
 
 f=1;
 return ;
 }
 for(int i=0;i&lt;4;i++)
 {
 
 node sk; 血的教训告诉我，一定要新生成节点，一定要
 sk.x=k.x+dir[i][0];
 sk.y=k.y+dir[i][1];
 if(vis[sk.x][sk.y])
 continue;
 if(a[sk.x][sk.y]==0&amp;&amp;isvalid(sk)||(sk.x==e.x&amp;&amp;sk.y==e.y&amp;&amp;isvalid(sk)))
 {
 
 if(vis[sk.x][sk.y]==true) 
 continue;
 node dd; 一定要，如果把他置为全局变量，很难控制其状态，保险起见，还是新生成一个节点
 dd.x=dir[i][0];
 dd.y=dir[i][1];
 if(dr.x==dd.x&amp;&amp;dr.y==dd.y)
 {
 
 //cout&lt;&lt;sk.x&lt;&lt;" "&lt;&lt;sk.y&lt;&lt;" "&lt;&lt;d&lt;&lt;endl; 
 DFS(sk,dd,d);
 }
 else
 {
 
 //cout&lt;&lt;sk.x&lt;&lt;" "&lt;&lt;sk.y&lt;&lt;" "&lt;&lt;d+1&lt;&lt;endl;
 DFS(sk,dd,d+1);
 }
 vis[sk.x][sk.y]=false;
 }
 }
}
int main()
{
 
 int i,j,t;
 //freopen("1.txt","r",stdin);
 while(~scanf("%d%d",&amp;n,&amp;m),n||m)
 {
 
 memset(vis,false,sizeof(vis));
 for(i=1;i&lt;=n;i++)
 {
 
 for(j=1;j&lt;=m;j++)
 {
 
 scanf("%d",&amp;a[i][j]);
 }
 }
 scanf("%d",&amp;t);
 while(t--)
 {
 
 scanf("%d%d%d%d",&amp;s.x,&amp;s.y,&amp;e.x,&amp;e.y);
 if(a[s.x][s.y]*a[e.x][e.y]==0||a[s.x][s.y]!=a[e.x][e.y]||s.x==e.y&amp;&amp;s.y==e.y)
 {
 
 printf("NO\n");
 continue;
 }
 
 if(a[s.x][s.y]==a[e.x][e.y])
 {
 
 f=0;
 ss.x=ss.y=0;
 DFS(s,ss,0);
 vis[s.x][s.y]=false; 这个起点记得要回溯
 if(f==1)
 printf("YES\n");
 else
 printf("NO\n");
 }
 }
 }
 return 0;
} </pre> </td> 
 </tr> 
 </tbody> 
</table>