蓝桥杯-小明的背包-python
题目描述小明有一个容量为 V 的背包。这天他去商场购物，商场一共有 N 件物品，第 i件物品的体积为 wi，价值为 vi。小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。输入描述输入第 1行包含两个正整数N,V，表示商场物品的数量和小明的背包容量。第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。1≤N≤10^2，1≤V≤10^3，1≤wi,vi≤10^3。输出描述输出一行整数表示小明所能获得的最大价值。输入输出样例示例 1输入1. 5 20
2. 1 6
3. 2 5
4. 3 8
5. 5 15
6. 3 3输出37运行限制最大运行时间：1s最大运行内存: 128M思路设计DP状态：定义二维数组dp[][],大小为N*C，dp[i][j]表示把前i个物品装入容量为j的背包中获得的最大值。我们把每个dp[i][j]都看成一个背包，背包的容量是j，装1~i这些物品。最后得到的dp[N][C]就是问题的答案。状态转移方程：我们考虑两种情况，如果i个物体比容积j大，则说明他肯定装不下，直接继承前i-1个物品装进容积j的背包情况即可。dp[i][j] = dp[i-1][j] 如果第i个物品比j小，能进背包。此时分为两种情况1.装第i个。从前i-1个物品的情况推广而来，前i-1个物品时dp[i-1][j]、第i个物品装进背包后，背包容积减少c[i]，价值增加w[i]dp[i][j] = dp[i-1][j-c[i]] + w[i] 2.不装第i个，那么dp[i][j] = dp[i-1][j] 我们取两种状态的最大值，得到状态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i])代码1. N=3011
2. dp = [[0 for i in range(N)] for j in range(N)]
3. w = [0 for i in range(N)]
4. c = [0 for i in range(N)]
6. def solve(n,C):
7. for i in range(1,n+1):
8. for j in range (0,C+1):
9. if c[i]>j :
10. dp[i][j] = dp[i-1][j]
11. else :
12. dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i])
13. return dp[n][C]
15. n, C = map(int, input().split())
16. for i in range(1, n+1):
17. c[i], w[i] = map(int, input().split())
18. print(solve(n, C))优化代码1. N=3011
2. dp=[[0 for i in range(N)] for j in range(2)]
3. w=[0 for i in range(N)]
4. c=[0 for i in range(N)]
6. def solve(n,C):
7. #由于当前状态只与前一个状态有关
8. #故设计滚动数组优化空间复杂度
9. now = 0
10. old =1
11. for i in range(1,n+1):
12. old,now = now,old #交换
13. for j in range (0,C+1):
14. if c[i] > j:
15. dp[now][j]=dp[old][j]
16. else:
17. dp[now][j] = max(dp[old][j], dp[old][j-c[i]]+w[i])
18. return dp[now][C]
20. n,C=map(int,input().split())
21. for i in range(1,n+1):
22. c[i],w[i]=map(int,input().split())
24. print(solve(n,C))
蓝桥杯-修改数组-python
问题描述给定一个长度为 N 的数组 A = [A1, A2, · · · AN]，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2, A3, · · · , AN。当修改 Ai 时，小明会检查 Ai 是否在 A1 ～ Ai-1 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在 A1 ～ Ai-1 中出现过。当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。【输入格式】第一行包含一个整数 N。第二行包含 N 个整数 A1, A2, · · · , AN 。【输出格式】输出 N 个整数，依次是最终的 A1, A2, · · · , AN。【样例输入】1. 5
2. 2 1 1 3 4【样例输出】2 1 3 4 5【评测用例规模与约定】对于 80% 的评测用例，1 ≤ N ≤ 10000。对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分思路使用并查集的算法，先寻找A[i]的根节点root，将root加入到答案中，再让s[root]这个集合的值加一，这一步的意义是：如果再次遇到之前遇到的数，可以直接在最终的答案里写入这个数根节点的值+1，即我们所求的值，这一步保证了下一次我们查询的正确性。这样循环往复，输入值之后就可以在最终的答案里加入正确的值。代码1. N=1000000
2. s=[] #并查集
4. #寻找根节点并简化路径
5. def find(x):
6. if x!=s[x]:
7. s[x]=find(s[x])
8. return s[x]
10. n=int(input())
11. A=input().split()
13. #初始化
14. for i in range(N):
15. s.append(i)
17. for i in range(n):
18. root=find(int(A[i]))
19. A[i]=root #A[i]等于根节点
20. s[root]=root+1 #属于这个集合的元素+1，为下一次寻找做准备
21. for i in A:
22. print(i,end=' ')
蓝桥杯-合根植物-python
问题描述w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？输入格式第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。格子的编号一行一行，从上到下，从左到右编号。比如：5 * 4 的小格子，编号：1 2 3 45 6 7 89 10 11 1213 14 15 1617 18 19 20样例输入5 4162 31 55 94 87 89 1010 1111 1210 1412 1614 1817 1815 1919 209 1313 17样例输出5样例说明其合根情况参考下图思路先假设所有植物都不连根，此时有m*n株植物使用并查集，设计查找函数find(),找到x所属的集合的根节点，设计合并函数merge()，先找到x合y的根节点，如果节点一致说明在一个集合中，即这两株植物已经连根了，返回false，节点不一致则说明不在一个集合中，没有连根，将这两株植物连在一起，并返回true。我们读入k行数据，合并每组数据（x,y),如果合并则ans--，最终输出ans代码1. def find(x):
2. if x!=s[x]:
3. s[x]=find(s[x])
4. return s[x]
6. #查找函数写法2
7. def find2(x):
8. if x == s[x]:
9. return x
10. else:
11. s[x] = find2(s[x])
12. return s[x]
14. def merge(x,y):
15. x=find2(x)
16. y=find2(y)
17. if x==y:
18. return False
19. s[y]=x
20. return True
22. m,n=map(int,input().split())
23. k=int(input())
25. #初始化数组
26. s=list(range(m*n+1))
28. ans=m*n
29. for i in range(k):
30. x,y=map(int,input().split())
31. if merge(x,y):
32. ans-=1
34. print(ans)
蓝桥杯-蓝桥幼儿园-python
题目描述蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：小明会用红绳连接两名学生，被连中的两个学生将成为朋友。小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。输入描述第 1 行包含两个正整数 N,M，其中 N表示蓝桥幼儿园的学生数量，学生的编号分别为 1∼N。之后的第 2∼M+1 行每行输入三个整数，op , x , y如果 op = 1，表示小明用红绳连接了学生 x和学生 y 。如果 op=2，请你回答小明学生 x 和 学生 y 是否为朋友。1≤N,M≤2*10^5 ,1≤x,y≤N。输出描述对于每个 op=2 的输入，如果 x和 y 是朋友，则输出一行 YES，否则输出一行 NO。输入输出样例示例 1输入1. 5 5
2. 2 1 2
3. 1 1 3
4. 2 1 3
5. 1 2 3
6. 2 1 2输出1. NO
2. YES
3. YES运行限制最大运行时间：3s最大运行内存: 256M思路： 采用并查集的方法。1。设计初始化函数init()，初始化数组s，将编号为1~N的N个对象划分为不相交的集合，在每个集合中选择一个元素代表整个集合。2.设计查找函数find(),通过递归的方法返回x的所在集合的代表元素。3.设置合并函数merge()，寻找x,y的根节点，如果根节点不一致，则改成一致主函数：当op==1时，读入x,y合并集合s[x],s[y]，使得s[x]=s[y]当op==2时，寻找x和y的根节点，通过比较根节点是否一致判断x和y是否在一个集合中。如果在，说明x,y是朋友，输出YES，否则输出NO。代码1. N=800000
2. s=[]
4. def init():
5. for i in range(N):
6. s.append(i)
8. def find(a):
9. if a!=s[a]:
10. s[a]=find(s[a])
11. return s[a]
13. def merge(x,y):
14. x=find(x)
15. y=find(y)
16. if x!=y:
17. s[x]=s[y]
19. n,m=map(int,input().split())
20. init()
21. for i in range(m):
22. op,x,y=map(int,input().split())
23. if op==1 :
24. merge(x,y)
25. if op==2 :
26. if find(x)==find(y):
27. print("YES")
28. else:
29. print("NO")
蓝桥杯-剪格子-python
问题描述如下图所示，3 x 3 的格子中填写了一些整数。我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。如果无法分割，则输出 0。输入格式程序先读入两个整数 m n 用空格分割 (m,n<10)。表示表格的宽度和高度。接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。输出格式输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。样例1.in1. 3 3
2. 10 1 52
3. 20 30 1
4. 1 2 3样例1.out3 思路采用深度优先搜索，从（0，0）开始向四个方向搜索，如果下一个点的坐标在区域内且未访问过，则搜索下一个点。边界条件:如果当前组合的和等于总和的一半且（0，0）点在这个组合中并且此时包含的格子数最小，那么他就是我们当前的最优解，递归回退。:如果当前组合的和大于总和的一半，那么就没有继续搜索的必要了，递归回退。代码1.
2. m,n=map(int,input().split())
4. a=[list(map(int,input().split())) for _ in range(n)]
5. #初始化访问列表
6. vis=[[1]*m for _ in range(n)]
8. sum1,ans=0,10000000
10. #计算总和
11. for i in range(n):
12. for j in range(m):
13. sum1+=int(a[i][j])
15. if sum1/2 != sum1//2:
16. print(0)
17. exit()
19. dir=[(1,0),(-1,0),(0,-1),(0,1)]
21. def dfs(x,y,step,sum2):
22. global sum1,ans
23. if sum2==sum1//2:
24. if vis[0][0]==0 and step<ans:
25. ans=step
26. return
28. if sum2>sum1//2:
29. return
31. vis[x][y]=0
32. for i in dir:
33. j,k=i
34. nx=x+j
35. ny=y+k
36. if nx>=0 and nx<n and ny>=0 and ny<m:
37. if vis[nx][ny]==1:
38. dfs(nx,ny,step+1,sum2+a[x][y])
39. vis[x][y]=1
41. dfs(0,0,0,0)
42. print(ans)
蓝桥杯-四平方和-python
题目描述四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去，就正好可以表示为 4 个数的平方和。比如：5 = 0^2 + 0^2 + 1^2 + 2^27 = 1^2 + 1^2 + 1^2 + 2^2对于一个给定的正整数，可能存在多种平方和的表示法。要求你对 4 个数排序：0≤a≤b≤c≤d并对所有的可能表示法按 a,b,c,d为联合主键升序排列，最后输出第一个表示法。输入描述程序输入为一个正整数 N(N<5×10^6)。输出描述要求输出 4 个非负整数，按从小到大排序，中间用空格分开输入输出样例示例输入12输出0 2 2 2思路：暴力寻找每一个数，做适当的剪枝处理代码：1. import math
2. n=int(input())
3. #确定边界，题目要求的数一定小于给定的数的开方
4. x=int((math.sqrt(n)))
6. #创建一个平方列表，减少寻找第四个数的时间
7. pf = [i ** 2 for i in range(0, x)]
9. def f(x):
10. #暴力搜索每一个数，进行可行性剪枝
11. for a in range(x+1):
12. flag=0
13. if a*a>n:
14. flag=1
15. for b in range(a,x+1):
16. if flag:
17. break
18. if a*a+b*b>n:
19. flag=1
20. for c in range(b,x+1):
21. z=n-a*a-b*b-c*c
22. if z<0:
23. flag=1
24. break
25. else:
26. if z in list:
27. ans=sorted([a,b,c,int(math.sqrt(z))])
28. return ans[0],ans[1],ans[2],ans[3]
29. a, b, c, d = f(x)
30. print(f"{a} {b} {c} {d}")
蓝桥杯-迷宫（19年）-python
题目描述本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。1. 010000
2. 000100
3. 001001
4. 110000迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中 D<L<R<U1. 01010101001011001001010110010110100100001000101010
2. 00001000100000101010010000100000001001100110100101
3. 01111011010010001000001101001011100011000000010000
4. 01000000001010100011010000101000001010101011001011
5. 00011111000000101000010010100010100000101100000000
6. 11001000110101000010101100011010011010101011110111
7. 00011011010101001001001010000001000101001110000000
8. 10100000101000100110101010111110011000010000111010
9. 00111000001010100001100010000001000101001100001001
10. 11000110100001110010001001010101010101010001101000
11. 00010000100100000101001010101110100010101010000101
12. 11100100101001001000010000010101010100100100010100
13. 00000010000000101011001111010001100000101010100011
14. 10101010011100001000011000010110011110110100001000
15. 10101010100001101010100101000010100000111011101001
16. 10000000101100010000101100101101001011100000000100
17. 10101001000000010100100001000100000100011110101001
18. 00101001010101101001010100011010101101110000110101
19. 11001010000100001100000010100101000001000111000010
20. 00001000110000110101101000000100101001001000011101
21. 10100101000101000000001110110010110101101010100001
22. 00101000010000110101010000100010001001000100010101
23. 10100001000110010001000010101001010101011111010010
24. 00000100101000000110010100101001000001000000000010
25. 11010000001001110111001001000011101001011011101000
26. 00000110100010001000100000001000011101000000110011
27. 10101000101000100010001111100010101001010000001000
28. 10000010100101001010110000000100101010001011101000
29. 00111100001000010000000110111000000001000000001011
30. 10000001100111010111010001000110111010101101111000 思路见注释代码1. from queue import Queue
3. #设计结构体，存储当前位置和到达此位置的路径
4. class node:
5. def __init__(self,x,y,path):
6. self.x=x
7. self.y=y
8. self.path=path
10. #输入地图
11. mp = []
12. for i in range(0, 30):
13. mp.append(input())
15. #字典序，字典序小的优先存入路径
16. k=['D','L','R','U']
17. #位置走向，对应字典序，D，L，R，U
18. dir=[(1,0),(0,-1),(0,1),(-1,0)]
19. #记录是否访问过
20. vis=[[0]*50 for i in range(30)]
22. #宽度优先搜索
23. def bfs():
24. start=node(0,0,"")
25. start.x,start.y,start.path=0,0,""
26. vis[0][0]=1
27. q=[]
28. q.append(start)
30. while len(q) != 0:
31. now=q[0]
32. q.pop(0)
33. #如果到达了终点
34. if now.x==29 and now.y==49:
35. print(now.path)
36. return
37. #向四个方向延伸
38. for i in range(4):
39. next = node(0,0,"")
40. next.x=now.x+dir[i][0]
41. next.y=now.y+dir[i][1]
42. #如果超出了边界，跳过
43. if next.x<0 or next.x>=30 or next.y<0 or next.y>=50:
44. continue
45. #如果已经访问过或者遇到了墙，跳过
46. if vis[next.x][next.y]==1 or mp[next.x][next.y]=='1':
47. continue
48. #标记该点
49. vis[next.x][next.y]=1
50. #记录路径
51. next.path=now.path+k[i]
52. #进入队列
53. q.append(next)
55. bfs()
蓝桥杯-跳蚱蜢-python
题目描述本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。如下图所示： 有 9 只盘子，排成 1 个圆圈。 其中 88 只盘子内装着 88 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1-8 换位，2-7换位,...），至少要经过多少次跳跃？运行限制最大运行时间：1s最大运行内存: 128M思路：如果让数字跳的话，情况太多，不容易编码，我们在这里让空盘子跳。将每次跳跃化简为空盘子与他相邻或者相隔一个的盘子交换位置。每次跳跃都可变化出四个新的排序，使用set()进行判重，如果已经搜索过当前的数字排序，则不需要继续搜索当前排序及其扩展的子排序。在具体实现过程过，我们使用广度优先搜索，一层一层往下搜索，如果当前层出现了“087654321”，则当前层的层数为我们所求的跳跃最小次数在代码中，我们假设空盘子是0，使用元组存储数据，格式为： （当前排序，0的位置，最少跳几次）代码1. def insertQueue(q:list,dir:int,news:tuple,vis:set):
2. pos=news[1] #0的位置
3. status=news[0] #当前的字符串
4. insertPos=(pos+dir+9) % 9 #交换的位置
5. t=list(status)
6. t[pos],t[insertPos]=t[insertPos],t[pos]
7. addstatus="".join(t)
8. if addstatus not in vis:
9. vis.add(addstatus)
10. q.append((addstatus,insertPos,news[2]+1))
14. q=[("012345678",0,0)]
15. vis=set()
16. vis.add("012345678")
17. while q:
18. news=q.pop(0)
19. if news[0]=="087654321":
20. print(news[2])
21. break
22. insertQueue(q,-2,news,vis)
23. insertQueue(q,-1,news,vis)
24. insertQueue(q,2,news,vis)
25. insertQueue(q,1,news,vis)
蓝桥杯-全球变暖-python
你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：….##….##……##.…####.…###.…其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。例如上图中的海域未来会变成如下样子：……………#………请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。输入格式第一行包含一个整数N。以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。输出格式一个整数表示答案。数据范围1≤N≤1000输入样例1：71. …
2. .##…
3. .##…
4. …##.
5. …####.
6. …###.
7. …输出样例1：1输入样例2：1. 9
3. .##.##…
4. .#####…
5. .##.##…
7. .##.#…
8. .#.###…
9. .#…#…
10. …输出样例2：1 思路对所给图片的每一个点进行宽度搜索。设置flag,如果flag==0,说明不被淹没，否则被淹没。如果一块地周围都是土地，那么他最终不会被淹没。标记搜算过的土地，避免重复搜索。搜索当前土地相邻的未标记的土地，直到搜完这块岛屿为止代码1. def bfs(i,j):
2. d=[(0,1),(0,-1),(1,0),(-1,0)]
3. q=[(i,j)]
4. vis[i][j]=1
5. global flag
6. while q:
7. t=q.pop(0)
8. tx,ty=t[0],t[1]
9. if mp[tx][ty+1]=='#' and mp[tx][ty-1]=='#' and mp[tx-1][ty]=='#' and mp[tx+1][ty]=='#':
10. flag=1
11. for n in range(4):
12. nx=tx+d[n][0]
13. ny=ty+d[n][1]
14. if vis[nx][ny]==0 and mp[nx][ny]=="#":
15. q.append((nx,ny))
16. vis[nx][ny]=1
18. n=int(input())
19. mp=[]
20. for i in range(n):
21. mp.append(list(input()))
23. vis = []
24. for i in range(n):
25. vis.append([0]*n)
27. ans=0
28. for i in range(n):
29. for j in range(n):
30. if vis[i][j]==0 and mp[i][j]=='#':
31. flag=0
32. bfs(i,j)
33. if flag==0:
34. ans+=1
35. print(ans)
蓝桥杯-迷宫（17年）-python
题目描述本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。X 星球的一处迷宫游乐场建在某个小山坡上。它是由 10×10 相互连通的小房间组成的。房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：L 表示走到左边的房间，R 表示走到右边的房间，U 表示走到上坡方向的房间，D 表示走到下坡方向的房间。X 星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！开始的时候，直升机把 100100 名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。迷宫地图如下：UDDLUULRULUURLLLRRRURRUURLDLRDRUDDDDUUUUURUDLLRRUUDURLRLDLRLULLURLLRDURDLULLRDDDUUDDUDUDLLULRDLUURRR请你计算一下，最后，有多少玩家会走出迷宫，而不是在里边兜圈子？如果你还没明白游戏规则，可以参看下面一个简化的 4x4 迷宫的解说图：运行限制最大运行时间：1s最大运行内存: 128M思路：深度搜索图表中每一个点，根据当前的位置的字母找到下一步要前去的点，如果能出去则cnt+=1,如果碰到了已经访问的点则说明在兜圈子，出不去。1. cnt = 0
2. ans=0
3. n=10
4. vis = [[0] * 10 for i in range(10)]
6. def dfs(i,j):
7. global cnt
8. if i<0 or j<0 or i>9 or j>9:
9. return True
10. if vis[i][j] : return False
11. cnt+=1
12. vis[i][j]=True
13. if mp[i][j]=='L': return dfs(i,j-1)
14. if mp[i][j]=='R': return dfs(i,j+1)
15. if mp[i][j]=='U': return dfs(i-1,j)
16. if mp[i][j]=='D': return dfs(i+1,j)
18. mp=[]
19. for i in range(n):
20. mp.append(input())
22. for i in list(range(10)):
23. for j in list(range(10)):
24. vis = [[0] * 10 for i in range(10)]#遍历每个坐标起点开始前都先清零
25. if(dfs(i, j)): ans+=1
27. print(ans)
