目录
可行性剪枝
达到目标进行剪枝
#给定整数a1、a2、、an,判断是否可以从中选出若干数,使它们的和恰好为k
n=int(input())
a=list(map(int,input().split()))
k=int(input())
# 已经从前i项得到了和sum,然后对于i项之后的进行分支
def dfs(i,sum):
if sum>k:#剪枝
return False
#如果前n项都计算过了,则返回sum是否与k相等
if i==n:
return sum==k
#不加a[i]的情况
if dfs(i+1,sum):
return True
#加上a[i]的情况
if dfs(i+1,sum+a[i]):
return True
#无论是否加上a[i]都不能凑成k就返回false
return False最优性剪枝
对于求最优解的一类问题,通常可以用最优性剪枝,比如在求解迷宫最短路的时候,如果发现当前的步数已经超过了当前最优解,那从当前状态开始的搜索都是多余的,因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝,可以省去大量冗余的计算。
此外,在搜索是否有可行解的过程中,一旦找到了一组可行解,后面所有的搜索都不必再进行了,这算是最优性剪枝的一个特例。
迷宫
n,m=map(int,input().split())
sx,sy=map(int,input().split())
gx,gy=map(int,input().split())
maze=[]
vis=[[0]*m for i in range(n)]
for i in range(n):
list1=list(input())
maze.append(list1)
#print(maze)
ans=float('inf')
def dfs(x,y,step):
global ans
if step>=ans:#剪枝
return
if x==gx and y==gy:
if step<ans:
ans=step
return
for dx,dy in [(1,0),(-1,0),(0,-1),(0,1)]:
nx=dx+x
ny=dy+y
if 0<=nx<n and 0<=ny<m and vis[nx][ny]!=1 and maze[nx][ny]!='#':
vis[x][y]=1
dfs(nx,ny,step+1)#必须走一步，故没有选与不选
vis[x][y]=0
return
dfs(sx,sy,0)
print(ans)重复性剪枝
对于某一些特定的搜索方式,一个方案可能会被搜索很多次,这样是没必要的。
再来看这个问题:
给定n个整数,要求选出K个数,使得选出来的K个数的和为sum。
如果搜索方法是每次从剩下的数里选一个数,一共搜到第k层,那么1,2,3这个选取方法能被搜索到6次,这是没必要的,因为我们只关注选出来的数的和,而根本不会关注选出来的数的顺序,所以这里可以用重复性剪枝。
我们强制规定选出来的数的位置是递增的,在搜索的时候,用一个参数来记录上一次选取的数的位置,那么此次选择我们从这个数之后开始选取,这样最后选出来的方案就不会重复了。
当然,搜索的效率也要比直接二进制枚举更高。
奇偶性剪枝
奇偶性剪枝我们先来看一道题目:
有一个nxm大小的迷宫。其中字符'S'表示起点,字符,D'表示出口,字符'x,表示墙壁,字符'.,表示平地。你需要从's'出发走到'D',每次只能向上下左右相邻的位置移动,并且不能走出地图,也不能走进墙壁。每次移动消耗1时间,走过路都会塌陷,因此不能走回头路或者原地不动。现在已知出口的大门会在T时间打开,判断在0时间从起点出发能否逃离迷宫。
数据范围n, m <?10, T <50。
样例
4 4 5
S.X.
..X.
..XD
....
输出
NO
我们只需要用DFS来搜索每条路线,并且只需搜到T时间就可以了(这是一个可行性剪枝)。但是仅仅这样也无法通过本题,还需考虑更多的剪枝。
如上图所示,将nxm的网格染成黑白两色。我们记每个格子的行数和列数之和为x,如果x为偶数,那么格子就是白色,反之奇数时为黑色。容易发现相邻的两个格子的颜色肯定不一样,也就是说每走一步颜色都会不一样。更普遍的结论是:走奇数步会改变颜色,走偶数步颜色不变。
那么如果起点和终点的颜色一样,而T是奇数的话,就不可能逃离迷宫。同理,如果起点和终点的颜色不一样,而T是偶数的话,也不能逃离迷宫。遇到这两种情况时,就不用进行DFS 了,直接输出"NO"
n,m,t=map(int,input().split())
maze=[]
vis=[[0]*m for i in range(n)]
for i in range(n):
list1=list(input())
maze.append(list1)
for i in range(n):
for j in range(m):
if maze[i][j]=='S':
sx,sy=i,j
if maze[i][j]=='D':
gx,gy=i,j
f=False
def dfs(x,y,cnt):
global f
if f:
return
if cnt==t and x==gy and y==gy:
f=True
return
for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
nx=dx+x
ny=dy+y
if 0<=nx<n and 0<=ny<m and vis[x][y]!=1 and maze[x][y]!='x':
vis[x][y]=1
dfs(nx,ny,cnt+1)
vis[x][y]=0
#偶数步不变，奇数步变
#起点和终点同色，sx+sy+gx+gy的和为偶数，要想到终点不能变色，故步数必须为偶数，sx+sy+gx+gy+t的和为偶数
#起点和终点异色，sx+sy+gx+gy的和为奇数，要想到终点必须变色，故步数必须为奇数，sx+sy+gx+gy+t的和为偶数
#其他状况均不能到达终点，故需满足sx+sy+gx+gy+t的和为偶数
if (sx+sy+gx+gy+t)%2!=0: #奇偶性剪枝
print('NO')
else:
dfs(0, 0, 0)
if f:
print('YES')
else:
print('NO')生日蛋糕
?
n,m=map(int,input().split())
#cnt:当前层数
#v:当前体积
#s:当前面积
#r:当前圆柱体半径的上界
#h:当前圆柱体高的上界
ans=float('inf')
vmin=[0]*(m+1)
for i in range(1,m+1):
vmin[i]=vmin[i-1]+i*i*i
def dfs(cnt,v,s,r,h):
global ans
if cnt==m:
if v==n:
ans=min(ans,s)
return
if vmin[m-cnt]+v>n:#可行性剪枝
return
if 2*(n-v)/r+s>ans:#最优性剪枝
return
for nr in range(r,m-cnt-1,-1):
for nh in range(h,m-cnt-1,-1):
ns=s+2*nr*nh
nv=v+nr*nr*nh
if nv>n:#可行性剪枝
continue
if cnt==0:
ns+=nr*nr
dfs(cnt+1,nv,ns,nr-1,nh-1)
r=int(n**0.5+0.5)#r最大时，h=1
dfs(0,0,0,r,n)
print(ans)
练习
找数字
n=int(input())
f=False
def dfs(m,cnt):
global f
if f:#最优性剪枝,当已经找到了一种可行性解的时候,就没有必要继续搜索了
return
if cnt>=19:#递归出口1,字符串的长度超出18。
return
if m%n==0:#递归出口2,找到了一种可行性答案。
f=True
print(m)
return
dfs(m*10+0,cnt+1)
dfs(m*10+1,cnt+1)
dfs(1,1)
蒜头君的旅游计划
马上就要放寒假了，蒜头君已经辛勤的工作一年了，打算和家人一起出去旅游放松放松。有经验的人一定知道，出去旅游前一定要有详细的旅行规划。蒜头君打算旅游 n 个城市，但并不是每条路线的花费都是一样的。蒜头君是一个勤俭节俭的人，他就在想怎么把所有的城市旅游一遍花费最小呢？（蒜头君不喜欢重复旅游同一个城市，也就是说已到达过的城市蒜头君是不会再次光临的）
输入格式
第一行输入一个整数 n (1≤n≤15)，表示有 n 个城市。
接下来有一个 n×n 的矩形，表示每两个城市之间的火车花费，每两个城市之间的花费不会超过 10000。
输出格式
输出一个整数，表示从 1 号城市把所有景点旅游一遍并且回到 1 号城市的最小花费。
样例输入
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
样例输出
8
n=int(input())
maze=[]
for i in range(n):
list1=list(map(int,input().split()))
maze.append(list1)
vis=[0]*n
ans=float("inf")
def dfs(x,sums,cnt):
global ans
if cnt==n:#递归出口
ans=min(ans,sums+maze[x][0])
return
if sums>=ans:#最优性剪枝
return
vis[x]=1#注意，从x到i，需先将x标记，防止for中再次选中
for i in range(n):
if vis[i]!=1:
dfs(i,sums+maze[x][i],cnt+1)
vis[x]=0
dfs(0,0,1)
print(ans)
因数最多的数
题目
思路
1.如何求因数的个数
在1到n的所有数中，满足2式值最大且1式不超过n的数为因数最多的数。
规定1式的值为x，2式的值为cnt
2.如何确定质数的范围
我们可以发现前 15个质数之积已经大于 10^16所以我们枚举这 15 个质数就足够了。
3.如何使得所求数字尽可能小
当越小的数字的次数越大时，所得数会最小，既：
p1 < p2 < p3 < p4 < …… < pk
a1>=a2>=a3>=a4>=……>=ak
72=（2**3）*（3**2）的因数个数=（3+1）*（2+1）
108=（2**2）*（3**3）的因数个数=（2+1）*（3+1）
72<108 但 因数个数却相等
既：
第 i个质数的次数一定大于第 i+1个质数的次数
t=int(input())
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]#15个一次方质因数相乘大于10^16，故只取前15
# n:给定的数值范围
# m:当前数最大可以到多少次方
# x:当前数已经有多大了
# d:当前选到了那个质数，p的下标
# cnt:当前的因子数量是多少
def dfs(n,m,x,d,cnt):#(数值范围，因数最大次方，当前数已经有多大了，p中下标，因数个数)
global maxn,ans
#如果当前因子数更大，更新因字数，最小数更新为当前数
if cnt>maxn:#因数个数大于目前最大值
maxn=cnt#更新因数最值
ans=x#更新目标值
#并未确定达到最值，故不进行return
elif cnt==maxn and x<ans:
ans=x
if d==15:
return#当所有质数都循环完时，return；
for i in range(1,m+1):#p中第d个元素选择要乘的次数
x=x*p[d]
if x>n:#之后的结果肯定都大于x，故break结束循环
break
dfs(n,i,x,d+1,cnt*(i+1))#传i是为了满足后面大的质因数的次方要小于前面小的，这样可以
#保证所得结果的因数是最大的，因为质因数越小，次方越大，因数越多。
for i in range(t):
n=int(input())
maxn = 0
ans=0
dfs(n,60,1,0,1)#由于2^60已经大于10^16，所以质数为2时，最大的次数为60次方
print(ans)
置换的玩笑
题目大意：
小蒜头又调皮了。这一次，姐姐的实验报告惨遭毒手。
姐姐的实验报告上原本记录着从 1 到 n 的序列，任意两个数字间用空格间隔。但是“坑姐”的蒜头居然把数字间的空格都给删掉了，整个数字序列变成一个长度为 1 到 100 的且首部没有空格的数字串。
现在姐姐已经怒了，蒜头找你写个程序快点把试验数据复原。
输入：
输入文件有一行，为一个字符串——被蒜头搞乱的实验数据。
字符串的长度在 1 到 100 之间。
输出：
输出共一行，为姐姐的原始测试数据—— 1 到 n 的输出。
任意两个数据之间有一个空格。
如果有多组符合要求的正确解，输出其中任意一组即可。
本题答案不唯一，符合要求的答案均正确
样例输入：
4111109876532
样例输出
4 1 11 10 9 8 7 6 5 3 2
解题思路：
因为字符串的长度不超过100，可以计算出n最大是54，我们只需要枚举一位数和两位数。
先通过字符串的长度计算出n，开一个数组标记枚举过的数，只有没标记过的数并且小于等于n才会存下来继续往后搜。
超时。。。
但是对于字符串s[x]+s[x+1],s[x:x+2]前者必须限制在x<=n-2，后者则不用。
s=input()
n=len(s)
vis=[0]*100
vis[0]=1
f=False
#x:现在在那一位
#cnt：已经分出多少数
def dfs(x,s1):
global f
if f:
return
if x>=n:
f=True
print(*s1)
return
if vis[int(s[x])]!=1:
vis[int(s[x])]=1
dfs(x+1,s1+[int(s[x])])
vis[int(s[x])]=0
if vis[int(s[x:x+2])]!=1:
vis[int(s[x:x+2])]=1
dfs(x + 2, s1+[int(s[x:x+2])])
vis[int(s[x:x + 2])] = 0
dfs(0,[])s=input()
n=len(s)
vis=[0]*100
vis[0]=1
f=False
#x:现在在那一位
#cnt：已经分出多少数
def dfs(x,s1):
global f
if f:
return
if x>=n:
f=True
print(*s1)
return
#print(s[x],s[x]+s[x+1],s[x:x+2])
if vis[int(s[x])]!=1:
vis[int(s[x])]=1
dfs(x+1,s1+[int(s[x])])
vis[int(s[x])]=0
if x<=n-2:
if vis[int(s[x]+s[x+1])]!=1:
vis[int(s[x]+s[x+1])]=1
dfs(x + 2, s1+[int(s[x]+s[x+1])])
vis[int(s[x]+s[x+1])]=0
dfs(0,[])优化
?因为序列从1开始递增排序，故只要确定好序列中数的个数就能确定最大值
s=input()
n=len(s)
vis=[0]*55
vis[0]=1
f=False
#x:现在在那一位
#cnt：已经分出多少数
def dfs(x,cnt,s1):
global f
if f:
return
if cnt==m:
f=True
print(*s1)
return
if x>=n:#剪枝
return
#print(s[x],s[x]+s[x+1],s[x:x+2])
if int(s[x])<=m:#可行性剪枝
if vis[int(s[x])]!=1:
vis[int(s[x])]=1
dfs(x+1,cnt+1,s1+[int(s[x])])
vis[int(s[x])]=0
if int(s[x:x+2]) <= m:#可行性剪枝
if vis[int(s[x:x+2])]!=1:
vis[int(s[x:x+2])]=1
dfs(x + 2,cnt+1,s1+[int(s[x:x+2])])
vis[int(s[x:x + 2])] = 0
if n<=9:
m=n#全部都是一位
else:
m=(n-9)//2+9#一位两
dfs(0,0,[])Betsy的旅行
?用普通DFS会超时
n=int(input())
sx,sy=0,0
gx,gy=n-1,n-1
vis=[[0]*n for i in range(n)]
def dfs(x,y,step):
global ans
if x==n-1 and y==0:
if step==n*n:
ans+=1
return
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = dx + x
ny = dy + y
if 0 <= nx < n and 0 <= ny < n and vis[nx][ny]!=1:
vis[x][y]=1
dfs(nx,ny,step+1)
vis[x][y]=0
ans=0
dfs(0,0,1)
print(ans)终点注意vis赋值的位置?
对vis赋值的位置还是有点迷(￣﹏￣；)
经过多方面的必对可以确定，有for的情况下在for外面赋值，无for就在dfs上下
n=int(input())
# maze=[[0]*n for i in range(n)]
last=[[0]*n for i in range(n)]
vis=[[0]*n for i in range(n)]
for i in range(n):
for j in range(n):
for di,dj in [(1,0),(-1,0),(0,1),(0,-1)]:
ni=di+i
nj=dj+j
if 0<=ni<n and 0<=nj<n:
last[i][j]+=1#统计每个格子周围有几个格子可以到达该格子
#该格子周围每走过一格，就减一，要想满足一进一出，则周围至少还要有1个未走过的格子
# for i in range(n):
# print(last[i])
def dfs(x,y,step):
#到达x，y点
global ans
# for i in range(n):
# print(vis[i])
# print(x,y)
#vis[x][y] = 1放这里的话如果到终点没达到step==n*n要求则无法令终点处的vis[x][y] = 0
if x==n-1 and y==0:
if step==n*n:
ans+=1
return
vis[x][y] = 1#注意放置位置
dir=0
#先对当前位置x，y的四周进行-1
bx,by=0,0
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = dx + x
ny = dy + y
if 0 <= nx < n and 0 <= ny < n and vis[nx][ny]!=1:
last[nx][ny] -= 1#对当前位置x，y的四周进行-1
if last[nx][ny]==1:#若周围减完1后存在=1的，就必须进入到该格子
dir=1
bx,by=nx,ny
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:#遍历第下一个点
nx = dx + x
ny = dy + y
if dir==1:
if nx!=bx or ny!=by:
continue
if 0 <= nx < n and 0 <= ny < n and vis[nx][ny]!=1:
r=0
f=True
for dx2, dy2 in [(1, 0), (-1, 0), (0, 1), (0, -1)]:#遍历第下一个点的周围
nx2 = dx2 + nx
ny2 = dy2 + ny
if 0 <= nx2 < n and 0 <= ny2 < n and vis[nx2][ny2] != 1:
if last[nx2][ny2]<2:#如果第二个点有=1的，说当nx跳到nx2时该值会减为0，故该nx不可取
f=False
break
elif last[nx2][ny2]==2:#第二个点必须走的点的个数
r+=1
if r<=1 and f:#nx可以走，且必须要走的点不能超过一个
#vis[x][y] = 1 #放这里不行
dfs(nx,ny,step+1)
#vis[x][y]=0 #放这里不行因为对于点x，y的所有点还没有遍历结束，不能让vis[x][y]=0
vis[x][y] = 0#注意放置位置
#回溯还原
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = dx + x
ny = dy + y
if 0 <= nx < n and 0 <= ny < n and vis[nx][ny]!=1:
last[nx][ny] += 1
ans=0
last[n-1][0]+=1
# print(last)
dfs(0,0,1)
print(ans)方块消消乐?
?
?
?
?
?关键信息：左下角为（0，0）；x横y纵；只能左右移动；有重力；棋盘为7行5列；颜色小于10种；x，y要小，g要大。
?注意棋盘按正常坐标轴是倒过来的
解决这道题首先要掌握两个要点：
1，单行单列连续同色块的清除
n=5
maze=[]
for i in range(n):
list1=list(map(int,input().split()))
maze.append(list1)
for i in range(n):
print(maze[i])
print()
def drop():
for x in range(5):
for y in range(1,7):
if maze[x][y]!=0 and maze[x][y-1]==0:
maze[x][y-1]=maze[x][y]
maze[x][y]=0
def clear():#注意x是行y是列
#查找所有横向连通块
flag=0
for x in range(3):#往右延申2格查找，故只需枚举前3列
for y in range(7):
if maze[x][y]!=0:#如果有颜色
x2=x
while x2+1<5 and maze[x2][y]==maze[x][y]:#在某一行中查找连续同色的个数
x2+=1
if x2-x>2:#行方向有超过3个的连续同色块
for tx in range(x,x2+1):#在连续色块中向上向下列搜索
up,dn=y,y
#向上查找连续同色个数
while up+1<7 and maze[tx][up+1]==maze[x][y]:
up+=1
# 向下查找连续同色个数
while dn-1>=0 and maze[tx][dn-1]==maze[x][y]:
dn-=1
#print(tx,up,dn)
if up-dn>=2:#列方向有超过3个的连续同色块
#print(dn,up+1)
for ty in range(dn,up+1):#开始清除列上连续同色块
maze[tx][ty]=0
print(1)
for tx in range(x,x2+1):#开始清除行上连续同色块
maze[tx][y]=0
#print(1)
flag=1
# 查找所有纵向向连通块
for x in range(5):#往右延申2格查找，故只需枚举前3列
for y in range(5):
if maze[x][y]!=0:#如果有颜色
y2=y
while y2+1<7 and maze[x][y2]==maze[x][y]:#在某一行中查找连续同色的个数
y2+=1
if y2-y>2:#行方向有超过3个的连续同色块
#print(y2)
for ty in range(y,y2+1):#在连续色块中向上向下列搜索
ri,lf=x,x
#向右查找连续同色个数
while ri+1<5 and maze[ri+1][ty]==maze[x][y]:
ri+=1
# 向左查找连续同色个数
while lf-1>=0 and maze[lf-1][ty]==maze[x][y]:
lf-=1
if ri-lf>=2:#行方向有超过3个的连续同色块
for tx in range(lf,ri+1):#开始清除行上连续同色块
maze[tx][ty]=0
#print(1)
for ty in range(y,y2+1):#开始清除列上连续同色块
maze[x][ty]=0
#print(1)
flag=1
if flag:#执行了清楚
return True
else:#没有执行清楚
return False
while clear():
print(1)
drop()
for i in range(n):
print(maze[i])
# 1 0 0 0 0 0 0
# # 0 0 0 0 0 0 0
# # 1 0 0 0 0 0 0
# # 2 3 2 0 0 0 0
# # 1 2 3 3 0 0 0
2， python中实现c语言中的memcpy（）函数
#dfs（）
#注意每个dfs中都会独立建立一个互不影响的temp，地址不一样。
temp=[[0]*7 for i in range(5)]#建立一个单独的内存地址用来存储此时maze的状态
for i in range(5):
for j in range(7):
temp[i][j]=maze[i][j]
#修改maze
#dfs（）
#回溯还原maze
for i in range(5):
for j in range(7):
maze[i][j]=temp[i][j]不知道错那了，/(ㄒoㄒ)/~~
PS：花了一天时间终于搞定了φ(゜▽゜*)?
n=int(input())
maze=[[0]*7 for i in range(5)]
for i in range(5):
list1=list(map(int,input().split()))
for j in range(len(list1)):
maze[i][j]=list1[j]
# for i in range(5):
# print(maze[i])
ans={}
f=False
def empty():
for i in range(len(maze)):
for j in range(len(maze[0])):
if maze[i][j]!=0:
return False
return True
def drop():
for x in range(5):
for y in range(1,7):
if maze[x][y]!=0 and maze[x][y-1]==0:
maze[x][y-1]=maze[x][y]
maze[x][y]=0
# num=[[-1]*10 for i in range(10)]
# for x in range(5):
# h=0
# for y in range(7):
# if maze[x][y]:
# h+=1
# num[x][h]=y #建立一个二维列表，将maze中非0的值从下往上依次排列
# for x in range(5):
# for y in range(7):
# if num[x][y]==-1:
# maze[x][y]=0
# else:
# maze[x][y]=maze[x][num[x][y]]
def clear():#注意x是行y是列
#查找所有横向连通块
# for i in range(5):
# print(maze[i])
# print('c')
flag=0
for x in range(3):#往右延申2格查找，故只需枚举前3列
for y in range(7):
if maze[x][y]!=0:#如果有颜色
x2=x
while x2+1<5 and maze[x2][y]==maze[x][y]:#在某一行中查找连续同色的个数
x2+=1
if x2-x>2:#行方向有超过3个的连续同色块
for tx in range(x,x2+1):#在连续色块中向上向下列搜索
up,dn=y,y
#向上查找连续同色个数
while up+1<7 and maze[tx][up+1]==maze[x][y]:
up+=1
# 向下查找连续同色个数
while dn-1>=0 and maze[tx][dn-1]==maze[x][y]:
dn-=1
#print(tx,up,dn)
if up-dn>2:#列方向有超过3个的连续同色块
#print(dn,up+1)
for ty in range(dn,up+1):#开始清除列上连续同色块
maze[tx][ty]=0
#print(1)
for tx in range(x,x2+1):#开始清除行上连续同色块
maze[tx][y]=0
#print(1)
flag=1
# 查找所有纵向向连通块
for x in range(5):#往右延申2格查找，故只需枚举前3列
for y in range(5):
if maze[x][y]!=0:#如果有颜色
y2=y
while y2+1<7 and maze[x][y2]==maze[x][y]:#在某一行中查找连续同色的个数
y2+=1
if y2-y>2:#行方向有超过3个的连续同色块
for ty in range(y,y2+1):#在连续色块中向上向下列搜索
ri,lf=x,x
#向右查找连续同色个数
while ri+1<5 and maze[ri+1][ty]==maze[x][y]:
ri+=1
# 向左查找连续同色个数
while lf-1>=0 and maze[lf-1][ty]==maze[x][y]:
lf-=1
if ri-lf>2:#行方向有超过3个的连续同色块
for tx in range(lf,ri+1):#开始清除行上连续同色块
maze[tx][ty]=0
for ty in range(y,y2+1):#开始清除列上连续同色块
maze[x][ty]=0
flag=1
# for i in range(5):
# print(maze[i])
# print('e')
if flag:#执行了清楚
return True
else:#没有执行清楚
return False
def dfs(step):
#print(step)
#print(step)
#print(1)
global f
#print(maze)
if f:
return
if step==n:
# print(ans)
# for i in range(5):
# print(maze[i])
if empty():
f=True
for i in range(n):
print(ans[i])#x,y,g
return
sum=[0]*11
for x in range(5):
for y in range(7):
sum[maze[x][y]]+=1
for i in range(1,11):
if sum[i]!=0 and sum[i]<3:#遍历所有颜色个数，有小于3的就无法清零
f=False
return
for x in range(5):
for y in range(7):
# for i in range(5):
# print(maze[i])
#print()
#print(maze[x][y])
if maze[x][y]==0:
continue
#右移
#print(x, y)
if x!=4:#如果坐标不在右边界，首先选择向右交换
if maze[x + 1][y]!=maze[x ][y]:
ans[step] = [x, y, 1] # 存步数
# 进行交换
# for i in range(5):
# print(maze[i])
# print()
# temp = maze.copy()
temp=[[0]*7 for i in range(5)]
for i in range(5):
for j in range(7):
temp[i][j]=maze[i][j]
t=maze[x][y]
maze[x][y]=maze[x + 1][y]
maze[x + 1][y]=t
#print(maze[x][y],maze[x + 1][y])
# for i in range(5):
# print(maze[i])
# print()
drop()#下落
# for i in range(5):
# print(maze[i])
# print()
while clear():
drop()
# for i in range(5):
# print(maze[i])
# print()
dfs(step+1)
for i in range(5):
for j in range(7):
maze[i][j]=temp[i][j]
#右移
if x!=0 and maze[x-1][y]==0:#坐标不在左边界，且左边为0才能换，不然不满足g最大
if maze[x -1][y]!=maze[x ][y]:
# for i in range(5):
# print(maze[i])
# print(1)
ans[step]=[x,y,-1]#存步数
# 进行交换
# temp =maze.copy()
temp=[[0]*7 for i in range(5)]
for i in range(5):
for j in range(7):
temp[i][j]=maze[i][j]
t=maze[x][y]
maze[x][y]=maze[x - 1][y]
maze[x - 1][y]=t
# for i in range(5):
# print(maze[i])
# print(2)
drop()
# for i in range(5):
# print(maze[i])
# print(3)
while clear():#如果执行了清除，就执行下落
# print(x)
drop()
# for i in range(5):
# print(maze[i])
# print(4)
dfs(step+1)
for i in range(5):
for j in range(7):
maze[i][j]=temp[i][j]
temp=[]
dfs(0)
# print(ans)
# if f!=True:
# print(-1)
# for i in range(5):
# print(maze[i])
# 2
# 0
# 1 0
# 1 0
# 2 3 2 0
# 1 2 3 3 0