题解 P1312 【Mayan游戏】
一道很经典的深搜题，要注意回溯之前保留原状态。然后就是输入一定要注意，如果是用for循环，记得要输入八个点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int ans,s[8][8],p[10][5],yan[11],cnt;
void xiao();
void bfs();
void dfs();
void diao()
{
int a,b,c=0;
for(int i=1;i<=5;i++)
{
for(int j=1;j<=7;j++)
{
if(s[i][j])
{
a=j;
while(!s[i][a-1]&&a>=2)
{
c=1;
s[i][a-1]=s[i][a];
s[i][a]=0;
a--;
}
}
}
}
if(c)
xiao();
return;
}
bool bfs(int a,int b,int c)
{
int i,j,k,head=0,tail=1,o[100][4],v=0,u=0;
o[0][1]=a;
o[0][2]=b;
while(head!=tail)
{
int x=o[head][1],y=o[head][2];
int a=y,b=y;
while(s[x][a+1]==c)
a++;
while(s[x][b-1]==c)
b--;
if(a-b>=2)
{
v=1;
for(i=b;i<=a;i++)
{
if(s[x][i])
{
u++;
s[x][i]=0;
o[tail][1]=x;
o[tail][2]=i;
tail++;
}
}
}
a=x;
b=x;
while(s[a+1][y]==c)
a++;
while(s[b-1][y]==c)
b--;
if(a-b>=2)
{
v=1;
for(i=b;i<=a;i++)
{
if(s[i][y])
{
u++;
s[i][y]=0;
o[tail][1]=i;
o[tail][2]=y;
tail++;
}
}
}
head++;
}
if(v)
{
yan[c]-=u;
return 1;
}
return 0;
}
void xiao()
{
int a,b,c=0;
for(int j=1;j<=5;j++)
for(int k=1;k<=7;k++)
if(s[j][k]&&yan[s[j][k]]>=3)
{
if(bfs(j,k,s[j][k]))
c=1;
}
else if(yan[s[j][k]]<3&&yan[s[j][k]]);
if(c)
diao();
return;
}
void dfs(int n)
{
int i,j,k,a,b,c=0,map[8][8],yan1[11];
for(i=1;i<=cnt;i++)
if(yan[i]<3&&yan[i])
return;
if(n>ans)
{
for(i=1;i<=cnt;i++)
if(yan[i])
return;
for(i=1;i<=n-1;i++)
cout<<p[i][1]-1<<" "<<p[i][2]-1<<" "<<p[i][3]<<endl;
exit(0);
}
for(i=1;i<=5;i++)
{
for(j=1;j<=7;j++)
{
if(s[i][j])
{
if(i<=4&&s[i][j]!=s[i+1][j])
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
map[i][j]=s[i][j];
for(int i=1;i<=cnt;i++)
yan1[i]=yan[i];
a=s[i][j];
s[i][j]=s[i+1][j];
s[i+1][j]=a;
p[n][1]=i;
p[n][2]=j;
p[n][3]=1;
diao();
xiao();
dfs(n+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
s[i][j]=map[i][j];
for(int i=1;i<=cnt;i++)
yan[i]=yan1[i];
}
if(!s[i-1][j]&&i>=2)
{
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
map[i][j]=s[i][j];
for(int i=1;i<=cnt;i++)
yan1[i]=yan[i];
s[i-1][j]=s[i][j];
s[i][j]=0;
p[n][1]=i;
p[n][2]=j;
p[n][3]=-1;
diao();
xiao();
dfs(n+1);
for(int i=1;i<=5;i++)
for(int j=1;j<=7;j++)
s[i][j]=map[i][j];
for(int i=1;i<=cnt;i++)
yan[i]=yan1[i];
}
}
}
}
}
int main()
{
int i,j;
cin>>ans;
for(i=1;i<=5;i++)
{
cin>>s[i][1];
if(s[i][1])
yan[s[i][1]]++;
for(j=2;j<=8;j++)
{
if(s[i][j-1])
{
cin>>s[i][j];
if(s[i][j])
yan[s[i][j]]++;
}
else break;
}
}
for(i=10;i>=1;i--)
if(yan[i])
break;
cnt=i;
dfs(1);
cout<<-1<<endl;
return 0;
}