在接下来的 H 行中，每行包括 W 个字符 。每个字符表示一块瓷砖的颜色，规则如下

文章插图
1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上 。该字符在每个数据集合中唯一出现一次 。
当在一行中读入的是两个零时，表示输入结束 。
输出格式
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖) 。
数据范围
1≤W,H≤20
输入样例：
6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
0 0
输出样例：
45
DIRC = [[-1, 0], [0, 1], [1, 0], [0, -1]]def dfs(x, y) :if g[x][y] == '#' : return 0 #障碍终止条件cnt = 1 #(x, y)基点的计数st[x][y] = Truefor i in range(4) :a, b = x + DIRC[i][0], y + DIRC[i][1]if a < 0 or a >= n or b < 0 or b >= m : continueif st[a][b] : continuecnt += dfs(a, b)return cntwhile True :m, n = map(int, input().split())if m == 0 and n == 0 : breakg = []for i in range(n) :g.append(input())st = [[False] * m for _ in range(n)]for i in range(n) :for j in range(m) :if g[i][j] == '@' :print(dfs(i, j))break
搜索顺序(回溯) 模板
考虑搜索顺序，就是回溯，要做到不重不漏
dfs(u) :if 最优性剪枝条件 : return ...if 终止条件 : return...#如果此层不会使用u则可在这里对树枝去重st[u] = Truefor i in path :if check(u, i) :#检查状态是否合法,可行性剪枝st[i] = True #树枝去重dfs(u + i)st[i] = False #恢复现场
思考
dfs回溯难点在于状态的保存
这里面有些技巧：
1、在回溯前预处理，首尾关系记录两两状态关系
2、对于状态的每个性质，分开存储
dfs的参数必须能够表示或者求出当前状态,这里的状态与终止条件与路径选择合法性有关
排列问题路径选择都是从头开始查找到没被遍历的节点
组合问题路径需要在上一层的基础上查找没有遍历的点
路径的选择，一般从已给序列中选择或者从以求出的路径中选择 。
做题思考方式
1、首先思考搜索顺序，即想一个搜索策略
2、确定搜索时需要了解的状态，状态与最终的结果、路径选择、可行性有关
3、剪枝
马走日
马在中国象棋以日字形规则移动 。
请编写一段程序，给定 n?m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点 。
输入格式
第一行为整数 T，表示测试数据组数 。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y 。
输出格式
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0 。
数据范围
1≤T≤9,
1≤m,n≤9,

文章插图
1≤n×m≤28,
0≤x≤n?1,
0≤y≤m?1
输入样例：
5 4 0 0
输出样例：
32
T = int(input())DIRC = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]def dfs(x, y, cnt) :global ansif cnt == n * m : # 终点条件ans += 1returnst[x][y] = Truefor i in range(8) : #路径选择a, b = x + DIRC[i][0], y + DIRC[i][1]if a < 0 or a >= n or b < 0 or b >= m : continueif st[a][b] : continue dfs(a, b, cnt + 1)st[x][y] = Falsefor t in range(T) :n, m, sx, sy = map(int, input().split())st = [[False] * m for _ in range(n)]ans = 0dfs(sx, sy, 1)print(ans)

• 上一页
• 1
• 2
• 3
• 下一页

• JavaScript图片廊——实现点击小图片栏显示大图
• 8 【CesiumJS入门】自定义鼠标指针图标——地球范围内实现
• 2 DataLake — 批流一体化的追风者
• 回溯算法基础---皇后问题，骑士游历，迷宫求解
• 商业公司主导下的非营利开源软件基金会之 ———— Eclipse 的成长和发展（
• PostgreSQL数据库锁机制——自旋锁浅析
• 高考志愿填报——网络安全专业解读
• NLP迁移学习——迁移学习的概念与方法
• 上 Unity3D塔防游戏开发——学习笔记
• 【数据结构】c语言基于堆栈实现回溯法自动走迷宫