棋盘格上有4中类型的方格，1表示起始方格，且只有一个起始方格；2表示结束方格，且只有一个结束方格；0表示中间要访问的方格；-1表示不能访问的方格，求在棋盘格上上下左右四个可移动方向从起始方格经过所有中间要访问的方格到达结束方格的路径条数。[1]首先遍历棋盘格，统计要走的方格数量，结束方格位置和起始方格位置，dfs(r,c,todo,grid)表示从grid[r,c]方格出发，还剩下todo-1个格子要走。dfs的算法流程：todo--，如果[r,c]方格是结束方格，若todo==0,计数加1,遇到结束方格就返回，不可能继续深搜。访问过grid[r,c]，标注grid[r,c]的值为3,表示已访问过，在四个方向上找[r,c]的邻居节点，如果邻居节点的值%2==0，表示需要访问但还未被访问，则dfs(邻居节点r,邻居节点c,todo,grid)，回溯完恢复[r,c]原来的状态，grid[r,c]=0
解数独题，数独棋盘格填了一些数字，使用程序解决数独。[2]判断数独的合法性题目在此。声明rows、columns和blocks布尔型数组，表示某区域是否有某数，valid布尔型表示是否有成型的数独，ts表示要填的空。首先rows、columns、blocks和valid都赋false,遍历9x9棋盘格，如果方格内容为空，ts.emplace_back(i,j)，否则，更新方格所在区域rows、columns和blocks存在某数。接着回溯填数，先从第一个空填起，如果填完所有空，valid赋为true,不再继续深搜，只要没填完，就依次尝试填1到9到空中，如果区域允许填进去，就填进去，标注区域已填某数，再填下一个空（深搜），恢复填空前的状态，标注区域没填某数（因为执行到此处，如果没填完空，说明这条分支进行不下去，那该空不能填某数，继续向下试，如果填完空，区域状态的改变也无法影响填空上的数，且深搜会很快结束）
一个含有“+”、“-”的字符串，a和b轮流翻转相邻的两个“+”为“-”，若某人无法找到可翻转的两个相邻“+”，则他被判为输。求在a和b均是最优策略玩游戏的情况下，a面对某一字符串后能否赢。[3]定义一个结构体，结构体接收字符串的引用，和一个索引i，这个结构体构造时设置字符串i号和i+1号字符为“-”，析构时设置这两处字符为“+”。定义从字符串到布尔值的映射，表示字符串的情景下要动的人是否取得胜利。回溯的内容：就是记忆化深搜，如果映射里有字符串对应的胜利状态，返回该状态；否则遍历字符串，若字符串和下一个字符串都为“+”，构造结构体，构造结构体后再看新的字符串能否胜利。遍历过程中如若产生翻转的新的字符串倒向下一个人的败局，则当前人会取得胜利（最优策略，倾向于走让他取得胜利的路径）；如若翻转的新的字符串都会使下一个人取得胜利，则本人一定输。复杂度更低O(n^2)的算法用到Sprague-Grundy的方法，见【C++】O(n^2) Sprague-Grundy （ACM博弈论相关SG函数） / [记忆化递归 + 回溯]
a和b轮流从1到n共n个数中不放回地拿出一个数，拿出的数的和第一次达到target时，判定游戏胜利。问双方均采用最优策略下a能否胜利。这里的难点是拿出的数的和的状态如何表示，可能多种情况取出的数的和相等，可能不同情况下取某个数对终局的影响不同，如何衡量某次取数时是胜态还是败态。应该编码已取的数到整数的位里面，已取那位为1,否则为0,这道题n的取值范围1<=n<=20，相等的编码数说明剩下局数如何胜负是等价的。如果n个数的和小于target,输，否则，会达到target,有赢的可能，深搜时的参数需要有n、target、已取数的状态编码和已取数的和，主要是运算状态对应的是胜态还是败态，只要次态有一个胜态，当前就是胜态，因为最优策略。关于胜态、败态、次态的含义见上一道题
参考链接：[1].980. 不同路径 III
[2].37. 解数独
[3].294. 翻转游戏 II
[4].464. 我能赢吗