【解题报告】洛谷P1312 Mayan游戏

题目链接

https://www.luogu.com.cn/problem/P1312

思路

直接大模拟

考虑每次向左向右移动，然后对于每次移动做出相应的操作，更改地图

在地图更改之前保存一个副本

然后对于每一个方块，我们进行一次搜索，每个方块向左向右移动

然后我们移动完了之后模拟重力，然后将方块全都落下来

然后消除应该消除的方块

同理继续搜索

每次搜索完了之后，应该回溯到之前的状态，方便之后的搜索

然后就是大模拟了，我干了一个半小时什么都没赶出来草

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int maxn=10;
struct movement{
	int x,y,dir;
}sol[maxn];
int n;
int m[maxn][maxn];
int lst[maxn][maxn][maxn];
int cla[maxn][maxn];
bool clear()
{
	bool flag=false;
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=7;j++)
		{
			if(i-1>=1&&i+1<=5&&m[i][j]==m[i-1][j]&&m[i][j]==m[i+1][j]&&m[i][j])
				cla[i-1][j]=cla[i+1][j]=cla[i][j]=flag=1;
			if(j-1>=1&&j+1<=7&&m[i][j]==m[i][j+1]&&m[i][j]==m[i][j-1]&&m[i][j])
				cla[i][j-1]=cla[i][j+1]=cla[i][j]=flag=1;
		}
	}
	if(!flag) return false;
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=7;j++)
		{
			if(cla[i][j])
				cla[i][j]=m[i][j]=0;
		}
	}
	return true;
}
bool check()
{
	for(int i=1;i<=5;i++)
	if(m[i][1]) 
	return false;
	return true;
}
void copy(int x)
{
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=7;j++)
		lst[x][i][j]=m[i][j];
	}
}
void gravity()
{
	for(int i=1;i<=5;i++)
	{
		int tmp=0;
		for(int j=1;j<=7;j++)
		{
			if(!m[i][j]) tmp++;
			else
			{
				if(!tmp) continue;
				m[i][j-tmp]=m[i][j];
				m[i][j]=0;
			}
		}
	}
}
void move(int i,int j,int x)
{
	int tmp=m[i][j];
	m[i][j]=m[i+x][j];
	m[i+x][j]=tmp;
	gravity();
	while(clear())
	gravity();
}
void dfs(int x)
{
	if(check())
	{
		for(int i=1;i<=n;i++)
		{
			cout<<sol[i].x<<" "<<sol[i].y<<" "<<sol[i].dir;
			cout<<'\n';
		}
		exit(0);
	}
	if(x==n+1) return ;
	copy(x);
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=7;j++)
		{
			if(m[i][j])
			{
				if(i+1<=5&&m[i][j]!=m[i+1][j])
				{
					move(i,j,1);
					sol[x].x=i-1,sol[x].y=j-1,sol[x].dir=1;
					dfs(x+1);
					for(int i=1;i<=5;i++)
					{
						for(int j=1;j<=7;j++)
						m[i][j]=lst[x][i][j];
						sol[x].x=sol[x].y=sol[x].dir=-1;
					}
				}
			}
			if(i-1>=1&&m[i-1][j]==0)
			{
				move(i,j,-1);
				sol[x].x=i-1,sol[x].y=j-1,sol[x].dir=-1;
				dfs(x+1);
				for(int i=1;i<=5;i++)
				{
					for(int j=1;j<=7;j++)
					m[i][j]=lst[x][i][j];
				}
				sol[x].x=sol[x].y=sol[x].dir=-1;
			}
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=8;j++)
		{
			int x;
			cin>>x;
			if(x==0) break;
			m[i][j]=x;
		}
	}
	memset(sol,0,sizeof(sol));
	dfs(1);
	cout<<-1<<'\n';
	return 0;
}