关键词：
/**
* 需求描述：
* 有一块N*M像素格的画板，初始状态空白，用‘X’表示
* 绘画规则为：每次选择一条斜线
* 如果斜线斜率为1，则选择一段格子，都涂为蓝色，用‘B’表示
* 如果斜线斜率为-1，则选择斜线中的一段格子，涂成黄色，用‘Y’表示
* 一个格子既涂成蓝色又涂成黄色，则变成绿色，用‘G’表示
* 已知一幅作品，求最少需要多少次操作完成这幅画
* *****************************************
* 输入：正整数N,M
* 画作：N行长度为M的字符串
*
*
* */
# include <stdio.h>
char str[60][60];
int m, n;
void dfs_Y(int x, int y) //斜率-1，涂黄色Y
if (x >= 0 && x < n && y >=0 && y < m && (str[x][y] == ‘Y‘ || str[x][y] == ‘G‘))
if(str[x][y] == ‘G‘)
str[x][y] = ‘B‘;
else
str[x][y] = ‘X‘;
dfs_Y(x - 1, y - 1);
dfs_Y(x + 1, y + 1);
return;
void dfs_B(int x, int y) //斜率1，涂蓝色B
if(x >= 0 && x < n && 0 <= y && y <m && (str[x][y] == ‘B‘ || str[x][y] == ‘G‘))
if (str[x][y] == ‘G‘)
str[x][y] = ‘Y‘;
else
str[x][y] = ‘X‘;
dfs_B(x + 1, y - 1);
dfs_B(x - 1, y + 1);
return;
int main(void)
int cnt;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", str[i]);
cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (str[i][j] == ‘Y‘)
dfs_Y(i, j);
cnt++;
else if (str[i][j] == ‘B‘)
dfs_B(i, j);
cnt++;
else if (str[i][j] == ‘G‘)
dfs_Y(i, j);
str[i][j] = ‘B‘;
dfs_B(i, j);
cnt += 2;
printf("%d
", cnt); //无论初始str是什么图案，执行完计算过程之后str全变成‘X‘
//测试用：
// for (int i = 0; i < 4; i++)
//
// for (int j = 0; j < 4; j++)
//
// printf("%c", str[i][j]);
//
// printf("
");
//
return 0;
回溯是啥
用爬山来比喻回溯，好比从山脚下找一条爬上山顶的路,起初有好几条道可走,当选择一条道走到某处时,又有几条岔道可供选择,只能选择其中一条道往前走,若能这样子顺利爬上山顶则罢了,否则走到一条绝路上时,只好返回到最近的一个路口,重新选择另一条没走过的道往前走。如果该路口的所有路都走不通,只得从该路口继续回返。照此规则走下去,要么找到一条到达山顶的路,要么最终试过所有可能的道,无法到达山顶。
回溯是一种穷举，但与brute force有一些区别，回溯带了两点脑子的，并不多，brute force一点也没带。
第一点脑子是回溯知道回头；相反如果是brute force,发现走不通立刻跳下山摔死，换第二条命从头换一条路走。
第二点脑子是回溯知道剪枝；如果有一条岔路上放了一坨屎，那这条路我们不走，就可以少走很多不必要走的路。
还有一些爱混淆的概念：递归，回溯，DFS。
回溯是一种找路方法，搜索的时候走不通就回头换路接着走，直到走通了或者发现此山根本不通。
DFS是一种开路策略，就是一条道先走到头，再往回走一步换一条路走到头，这也是回溯用到的策略。在树和图上回溯时人们叫它DFS。
递归是一种行为，回溯和递归如出一辙，都是一言不合就回到来时的路，所以一般回溯用递归实现；当然也可以不用，用栈。
以下以回溯统称，因为这个词听上去很文雅。
识别回溯
判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。
一般回溯的问题有三种：
-
Find a path to success 有没有解
-
Find all paths to success 求所有解
-
求所有解的个数
-
求所有解的具体信息
-
-
Find the best path to success 求最优解
理解回溯：给一堆选择, 必须从里面选一个. 选完之后我又有了新的一组选择. This procedure is repeated over and over until you reach a final state. If you made a good sequence of choices, your final state is a goal state; if you didn‘t, it isn‘t.
回溯可以抽象为一棵树，我们的目标可以是找这个树有没有good leaf，也可以是问有多少个good leaf，也可以是找这些good leaf都在哪，也可以问哪个good leaf最好，分别对应上面所说回溯的问题分类。
good leaf都在leaf上。good leaf是我们的goal state，leaf node是final state，是解空间的边界。
对于第一类问题(问有没有解)，基本都是长着个样子的，理解了它，其他类别迎刃而解：
boolean solve(Node n)
if n is a leaf node
if the leaf is a goal node, return true
else return false
else
for each child c of n
if solve(c) succeeds, return true
return false
请读以下这段话以加深理解：
Notice that the algorithm is expressed as a boolean function. This is essential to understanding the algorithm. If solve(n) is true, that means node n is part of a solution--that is, node n is one of the nodes on a path from the root to some goal node. We say that n is solvable. If solve(n) is false, then there is no path that includes n to any goal node.
还不懂的话请通读全文吧：Backtracking - David Matuszek
关于回溯的三种问题，模板略有不同，
第一种，返回值是true/false。
第二种，求个数，设全局counter，返回值是void；求所有解信息，设result，返回值void。
第三种，设个全局变量best，返回值是void。
第一种：
boolean solve(Node n)
if n is a leaf node
if the leaf is a goal node, return true
else return false
else
for each child c of n
if solve(c) succeeds, return true
return false
第二种：
void solve(Node n)
if n is a leaf node
if the leaf is a goal node, count++, return;
else return
else
for each child c of n
solve(c)
第三种：
void solve(Node n)
if n is a leaf node
if the leaf is a goal node, update best result, return;
else return
else
for each child c of n
solve(c)
题目
八皇后 N-Queens
问题
1.给个n，问有没有解；
2.给个n，有几种解；(Leetcode N-Queens II)
3.给个n，给出所有解；(Leetcode N-Queens I)
解答
1.有没有解
怎么做：一行一行的放queen，每行尝试n个可能，有一个可达，返回true；都不可达，返回false.
边界条件leaf:放完第n行 或者 该放第n+1行(出界，返回)
目标条件goal:n行放满且isValid，即目标一定在leaf上
helper函数：
boolean solve(int i, int[][] matrix)
在进来的一瞬间，满足property：第i行还没有被放置，前i-1行放置完毕且valid
solve要在给定的matrix上试图给第i行每个位置放queen。
public static boolean solve1(int i, List<Integer> matrix, int n)
if (i == n)
if (isValid(matrix))
return true;
return false;
else
for (int j = 0; j < n; j++)
matrix.add(j);
if (isValid(matrix)) //剪枝
if (solve1(i + 1, matrix, n))
return true;
matrix.remove(matrix.size() - 1);
return false;
2.求解的个数
怎么做：一行一行的放queen，每行尝试n个可能。这回因为要找所有，返回值就没有了意义，用void即可。在搜索时，如果有一个可达，仍要继续尝试；每个子选项都试完了，返回.
边界条件leaf:放完第n行 或者 该放第n+1行(出界，返回)
目标条件goal:n行放满且isValid，即目标一定在leaf上
helper函数：
void solve(int i, int[][] matrix)
在进来的一瞬间，满足property：第i行还没有被放置，前i-1行放置完毕且valid
solve要在给定的matrix上试图给第i行每个位置放queen。
这里为了记录解的个数，设置一个全局变量(static)int是比较efficient的做法。
public static void solve2(int i, List<Integer> matrix, int n)
if (i == n)
if (isValid(matrix))
count++;
return;
else
for (int j = 0; j < n; j++)
matrix.add(j);
if (isValid(matrix)) //剪枝
solve2(i + 1, matrix, n);
matrix.remove(matrix.size() - 1);
3.求所有解的具体信息
怎么做：一行一行的放queen，每行尝试n个可能。返回值同样用void即可。在搜索时，如果有一个可达，仍要继续尝试；每个子选项都试完了，返回.
边界条件leaf:放完第n行 或者 该放第n+1行(出界，返回)
目标条件goal:n行放满且isValid，即目标一定在leaf上
helper函数：
void solve(int i, int[][] matrix)
在进来的一瞬间，满足property：第i行还没有被放置，前i-1行放置完毕且valid
solve要在给定的matrix上试图给第i行每个位置放queen。
这里为了记录解的具体情况，设置一个全局变量(static)集合是比较efficient的做法。
当然也可以把结果集合作为参数传来传去。
public static void solve3(int i, List<Integer> matrix, int n)
if (i == n)
if (isValid(matrix))
result.add(new ArrayList<Integer>(matrix));
return;
else
for (int j = 0; j < n; j++)
matrix.add(j);
if (isValid(matrix)) //剪枝
solve3(i + 1, matrix, n);
matrix.remove(matrix.size() - 1);
优化
上面的例子用了省空间的方法。
由于每行只能放一个，一共n行的话，用一个大小为n的数组，数组的第i个元素表示第i行放在了第几列上。
Utility(给一个list判断他的最后一行是否和前面冲突):
public static boolean isValid(List<Integer> list)
int row = list.size() - 1;
int col = list.get(row);
for (int i = 0; i <= row - 1; i++)
int row1 = i;
int col1 = list.get(i);
if (col == col1)
return false;
if (row1 - row == col1 - col)
return false;
if (row1 - row == col - col1)
return false;
return true;
递归：就是出现这种情况的代码： （或者说是用到了栈）
解答树角度：在dfs遍历一棵解答树
优点：结构简洁
缺点：效率低，可能栈溢出
递归的一般结构：
-
void f()
-
-
if(符合边界条件)
-
-
///////
-
return;
-
-
-
//某种形式的调用
-
f();
-
回溯：递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。
解答树角度：带回溯的dfs遍历一棵解答树
回溯的一般结构：
-
void dfs(int 当前状态)
-
-
if(当前状态为边界状态)
-
-
记录或输出
-
return;
-
-
for(i=0;i<n;i++) //横向遍历解答树所有子节点
-
-
//扩展出一个子状态。
-
修改了全局变量
-
if(子状态满足约束条件)
-
-
dfs(子状态)
-
-
恢复全局变量//回溯部分
-
-
BFS和DFS是相似。
BFS（显式用队列）
DFS（隐式用栈）（即递归）
当然，对于DFS，用递归可能会造成栈溢出，所以也可以更改为显示栈。
BFS：典型例题：P101 对于二叉树的层次遍历，P108对于图的走迷宫最短路径
-
将（起始）首节点加入队列： q.push(head);
-
标记首节点已经被访问： isvisited[head]=true;
-
以下自动反应： while(!q.empty())
-
-
int temp=q.front();
-
q.pop();
-
访问temp，并标记temp已被访问过，将temp的子相关节点加入队列
-
q.push(temp相关节点);
-
DFS:典型例题：P107黑白图像
格式：将所有节点遍历一遍，在遍历每个节点是，DFS的遍历该节点相关的所有节点
-
void dfs(int x, int y)
-
-
if(!mat[x][y] || vis[x][y]) return; // 曾经访问过这个格子，或者当前格子是白色
-
vis[x][y] = 1; // 标记(x,y)已访问过
-
dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1);
-
dfs(x-1,y); dfs(x,y+1);
-
dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 递归访问周围的八个格子
-
-
主循环：
-
for(int i = 1; i <= n; i++)
-
for(int j = 1; j <= n; j++)
-
if(!vis[i][j] && mat[i][j])
-
-
count++;
-
dfs(i,j);
-
// 找到没有访问过的黑格
Ref:
http://www.cnblogs.com/HectorInsanE/archive/2010/11/09/1872656.html
赏月斋源码共享计划第二期
需求描述：有m个任务，第i个任务需要xi时间去完成，难度等级为yi有n台机器，每台机器最长工作时间为zi，机器等级wi一个任务只能交给一台机器，且如果机器的最长工作时间小于任务所需时间，则不能完成若完成任务，获得收... 查看详情
赏月斋源码共享计划第七期括号匹配
题目：字符串中有括号”()[]”，设计算法，判断该字符串是否有效括号必须以正确的顺序配对，如：“()”、“()[]”是有效的，但“([)]”无效 解法一：#coding=utf-8frompythonds.basic.stackimportStack#栈可以不用此包，入栈append，出栈... 查看详情
暑假第三期---思维题3(代码片段)
A-VanyaandTable–CodeForces552ATimeLimit:2000MSMemoryLimit:262144KB64bitIOFormat:%I64d&%I64uDescriptionVanyahasatableconsistingof100rows,eachrowcontains100cells.Therowsarenumberedbyintegersfrom1to1 查看详情
aqs源码剖析第三篇--共享模式(代码片段)
AQS源码剖析第三篇--共享模式CountDownLatch源码分析await源码分析countDown源码分析CyclicBarrier源码分析Semaphore参考系列文章:AQS源码剖析第一篇—全貌概览AQS源码剖析第二篇–公平与非公平,条件队列和线程中断这篇，我们的关注点... 查看详情
第三期行为规划——14.计划计算时间
...定和整个系统体系结构的重要性不允许比较慢的模块行为计划者记录其他更快速组件的正常运行。让我们花一秒钟来谈谈所谓的排班问题以及如何在自驾车中处理。此图显示了在行为模块的两个处理周期中发生的情况。如您所见... 查看详情
mysql第三期基本查询语句结构(代码片段)
文章目录1.SQL概述1.1SQL背景知识1.2SQL分类2.SQL语言的规则与规范2.1基本规则2.2SQL大小写规范（建议遵守）2.3注释2.4命名规则（暂时了解）3.基本的SELECT语句3.1查询基本结构3.2列的别名3.3去除重复行扩展windowscmd命令下... 查看详情
5万字typescript入门系列（第三期）（建议收藏）(代码片段)
极客江南：一个对开发技术特别执着的程序员，对移动开发有着独到的见解和深入的研究，有着多年的iOS、Android、HTML5开发经验，对NativeApp、HybridApp、WebApp开发有着独到的见解和深入的研究,除此之外还精通JavaScrip... 查看详情
5万字typescript入门系列（第三期）（建议收藏）(代码片段)
极客江南：一个对开发技术特别执着的程序员，对移动开发有着独到的见解和深入的研究，有着多年的iOS、Android、HTML5开发经验，对NativeApp、HybridApp、WebApp开发有着独到的见解和深入的研究,除此之外还精通JavaScrip... 查看详情
用户登录项目第三期——用户登录(代码片段)
前言在之前的两期中，我们完成了Mysql数据库表的创建以及Html界面的设计，本期我们将完成最后一部分——用户登录功能的设计。其主要用到：JDBC，Servlet，Java面向对象等知识其基本原理：登录界面提交后... 查看详情
2021第三期被面试官最爱问的作用域与作用域链(代码片段)
2021第三期。本文继上篇文章详细讲解的JavaScript执行上下文继续深入作用域与作用域链。在上一篇文章中《【2021第二期】简而不单，单而不简的执行上下文》，主要分享到了执行上下文的概念，而作用域和作用域链是... 查看详情
c++初学必练基础题第三期(代码片段)
前言Hello！小伙伴！非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～ 自我介绍ଘ(੭ˊᵕˋ)੭昵称：海轰标签：程序猿｜C++选手｜学生简介：因C语言结识编程，... 查看详情
第三期轨迹生成——3.运动规划算法的属性
在讨论计划算法时，有两个重要的属性我们想谈谈。第一个被称为完整性。这意味着如果通过乘法问题存在解决方案，规划者会发现它。如果解决方案不存在，计划者将终止并报告没有解决方案。所以，请考虑以下两种情况。在... 查看详情
#腾讯云·未来开发者云梯计划#第三期上线啦！全国5000个免费云认证培训考试名额开放报名中！
11年前，著名硅谷投资人马克·安德森曾表示“软件正在吞噬世界”，然而他只预言了故事的开头。10多年过去，作为有效推动企业数字化转型步伐的核心技术，云原生已成为正在吞噬世界的“大鱼”，被开发... 查看详情
第十四届蓝桥杯第三期模拟赛python(代码片段)
第十四届蓝桥杯第三期模拟赛【python】文章目录第十四届蓝桥杯第三期模拟赛【python】✨最小的十六进制（python的16进制）❓️问题描述答案提交🧠思路🖥︎参考答案✨Excel的列（进制转化）❓️问题描述... 查看详情
技术实践第三期｜hashtag在redis集群环境下的使用(代码片段)
简介：欢迎了解友盟+技术干货第三期内容：Redis集群环境如何按照前缀批量删除缓存。希望能对开发者们在实际应用中有所帮助。一、背景数据源列表添加缓存支持，types字段可传多值，如app,mini,web等，会... 查看详情
容器云原生devops学习笔记——第三期：从零搭建ci/cd系统标准化交付流程(代码片段)
暑期实习期间，所在的技术中台—效能研发团队规划设计并结合公司开源协同实现符合DevOps理念的研发工具平台，实现研发过程自动化、标准化；实习期间对DevOps的理解一直懵懵懂懂，最近观看了阿里专家带你玩... 查看详情
容器云原生devops学习笔记——第三期：从零搭建ci/cd系统标准化交付流程(代码片段)
暑期实习期间，所在的技术中台—效能研发团队规划设计并结合公司开源协同实现符合DevOps理念的研发工具平台，实现研发过程自动化、标准化；实习期间对DevOps的理解一直懵懵懂懂，最近观看了阿里专家带你玩... 查看详情
第十四届蓝桥杯模拟赛（第三期）java组个人题解(代码片段)
第十四届蓝桥杯模拟赛（第三期）Java组个人题解今天做了一下第三期的校内模拟赛，有些地方不确定，欢迎讨论和指正~🌷仰望天空，妳我亦是行人.✨🦄个人主页——微风撞见云的博客🎐🐳... 查看详情