第5章〓回溯法
5.1LintCode1353——根结点到叶子
结点求和★★
问题描述: 给定仅包含数字0～9的二叉树，每个根结点到叶子结点的路径可以表示为数字。例如roottoleaf路径1>2>3，它代表数字123。设计一个算法求所有根结点到叶子结点的数字的总和。要求设计如下成员函数:
int sumNumbers(TreeNode *root) { }
解: 将二叉树看成一棵解空间树，从根结点开始搜索所有的结点，用cursum累计路径表示的数字，每次到达一个叶子结点时将cursum累计到ans中，最后返回ans即可。对应的回溯算法如下:
class Solution {
int ans;
public:
int sumNumbers(TreeNode *root) {
if(root==NULL) return 0;
ans=0;
dfs(root,root->val);
return ans;
}
void dfs(TreeNode *root,int cursum) {
if(root->left==NULL && root->right==NULL)
ans+=cursum;
else {
if(root->left!=NULL) {
cursum=cursum*10+root->left->val;
dfs(root->left,cursum);
cursum=(cursum-root->left->val)/10;
}
if(root->right!=NULL) {
cursum=cursum*10+root->right->val;
dfs(root->right,cursum);
cursum=(cursum-root->right->val)/10;
}
}
}
};
上述程序提交后通过，执行用时为41ms，内存消耗为5.52MB。
5.2LintCode802——数独★★★
问题描述: 数独是一种逻辑性的数字填充游戏，玩家需将数字填进每一格，而每行、每列和每个宫（即3×3的大格）恰好有1~9的所有数字。游戏设计者会提供一部分的数字，使谜题只有一个答案。一个已解答的数独其实是一种多了宫的限制的拉丁方阵，因为同一个数字不可能在同一行、列或宫中出现多于一次。编写一个程序，通过填充空单元来解决数独谜题，空单元由数字0表示，可以认为只有一个唯一的解决方案。例如，给定的数独谜题如下:
{{0，0，9，7，4，8，0，0，0}，
{7，0，0，0，0，0，0，0，0}，
{0，2，0，1，0，9，0，0，0}，
{0，0，7，0，0，0，2，4，0}，
{0，6，4，0，1，0，5，9，0}，
{0，9，8，0，0，0，3，0，0}，
{0，0，0，8，0，3，0，2，0}，
{0，0，0，0，0，0，0，0，6}，
{0，0，0，2，7，5，9，0，0}}
返回结果如下:
{{5，1，9，7，4，8，6，3，2}，
{7，8，3，6，5，2，4，1，9}，
{4，2，6，1，3，9，8，7，5}，
{3，5，7，9，8，6，2，4，1}，
{2，6，4，3，1，7，5，9，8}，
{1，9，8，5，2，4，3，6，7}，
{9，7，5，8，6，3，1，2，4}，
{8，3，2，4，9，1，7，5，6}，
{6，4，1，2，7，5，9，8，3}}
要求设计如下成员函数:
void solveSudoku(vector<vector<int>> &b) { }
解法1: 从位置(i，j)为(0，0)开始搜索，先搜索第i行的每个列，当j=9时转向下一行，每个b［i］［j］=0的位置检测是否可以放置d（1≤d≤9），相当于每个位置9选择1，当i=9时说明找到一个解，返回true。对应的程序如下:
class Solution {
public:
void solveSudoku(vector<vector<int>> &b) {
dfs(b,0,0);
}
bool dfs(vector<vector<int>> &b,int i,int j) {
if (i==9) {
return true;
}
if (j==9) {
return dfs(b,i+1,0);
}
if (b［i］［j］!=0) {
return dfs(b,i,j+1);
}
for (int d=1;d<=9;d++) {
if (!valid(b,i,j,d)) {
continue;
}
b［i］［j］=d;
if (dfs(b,i,j+1)) {
return true;
}
b［i］［j］=0;
}
return false;
}
bool valid(vector<vector<int>> &b, int i,int j,int d) { //检测b［i］［j］是否能够放置d
for (int x=0;x<9;x++) { //检测同列是否有d
if (b［x］［j］==d) {
return false;
}
}
for (int y=0;y<9;y++) { //检测同行是否有d
if (b［i］［y］==d) {
return false;
}
}
int row=i-i%3,col=j-j%3; //大格的左上角(row,col)
for (int x=0;x<3;x++) { //检测大格是否有d
for (int y=0;y<3;y++) {
if (b［row+x］［col+y］==d) {
return false;
}
}
}
return true;
}
};
上述程序提交后通过，执行用时为81ms，内存消耗为5.49MB。
解法2: 采用一维序号，将9×9的棋盘方格按行/列编号为0～80，即(i，j)的一维序号k=9i+j，反过来，i=k/9，j=k%9。i从0开始搜索，当i≥81时得到一个解，存放在ans中，最后置b=ans（如果不做这样的置换，返回时b仍然为初始值）。对应的程序如下:
class Solution {
vector<vector<int>> ans;
bool flag;
public:
void solveSudoku(vector<vector<int>> &b) {
flag=false;
dfs(b,0);
b=ans;
}
void dfs(vector<vector<int>> &b,int k) {
if(k>=81) {
ans=b;
flag=true;
}
else if(!flag) {
int i=k/9,j=k%9; //序号k转换成行/列编号
if(b［i］［j］!=0)
dfs(b,k+1);
else {
for(int d=1;d<=9;d++) {
if(valid(b,i,j,d)){
b［i］［j］=d;
dfs(b,k+1);
b［i］［j］=0;
}
}
}
}
}
bool valid(vector<vector<int>> &b,int i,int j,int d) { //检测b［i］［j］是否能够放置d
for (int x=0;x<9;x++) { //检测同列是否有d
if (b［x］［j］==d) {
return false;
}
}
for (int y=0;y<9;y++) { //检测同行是否有d
if (b［i］［y］==d) {
return false;
}
}
int row=i-i%3,col=j-j%3; //大格的左上角(row,col)
for (int x=0;x<3;x++) { //检测大格是否有d
for (int y=0;y<3;y++) {
if (b［row+x］［col+y］==d) {
return false;
}
}
}
return true;
}
};
上述程序提交后通过，执行用时为82ms，内存消耗为5.45MB。
5.3LintCode135——数字组合★★
问题描述: 给定一个候选整数的集合candidates和一个目标值target，所有整数（包括 target）都是正整数，设计一个算法求candidates中所有和为target的组合，在同一个组合中，candidates 中的某个整数出现的次数不限，返回的每一个组合内的整数必须是非降序的，返回的所有组合之间可以是任意顺序，解集不能包含重复的组合。例如，candidates={2，3，6，7}，target=7，答案是{{7}，{2，2，3}}。要求设计如下成员函数:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) { }
解法1: 采用完全背包的求解思路，首先对candidates数组递增排序，用i遍历该数组，每个元素有3种选择，即不选择candidates［i］、选择candidates［i］后下一次仍然选择candidates［i］、选择candidates［i］后下一次不再选择candidates［i］。对应的程序如下:
class Solution {
public:
set<vector<int>> myset;
vector<int> x;
vector<int> a;
int t,n;
vector<vector<int>> combinationSum(vector<int> &candidates,int target) {
a=candidates;
t=target;
n=a.size();
sort(a.begin(),a.end());
dfs(0,0);
vector<vector<int>> ans;
for(auto e:myset)
ans.push_back(e);
return ans;
}
void dfs(int cursum,int i) { //回溯算法
if(i>=n) {
if(cursum==t) //找到一个解
myset.insert(x);
}
else {
dfs(cursum,i+1); //不选择a［i］
if(cursum+a［i］<=t) { //剪支
x.push_back(a［i］);
dfs(cursum+a［i］,i); //选择a［i］，然后继续选择a［i］
x.pop_back();
}
if(cursum+a［i］<=t) { //剪支
x.push_back(a［i］);
dfs(cursum+a［i］,i+1); //选择a［i］,然后选择下一个元素
x.pop_back();
}
}
}
};
上述程序提交后通过，执行用时为41ms，内存消耗为5.74MB。
解法2: 由candidates去重得到数组a，利用《教程》中5.2.2节求幂集的解法2的思路，在a中求子集和为target的序列。对应的回溯法程序如下:
class Solution {
public:
vector<vector<int>> ans;
vector<int> x;
vector<int> a;
int n;
vector<vector<int>> combinationSum(vector<int> &candidates,int target) {
if(candidates.size()==0)
return ans;
sort(candidates.begin(),candidates.end()); //排序
a.push_back(candidates［0］);
for(int i=1;i<candidates.size();i++) { //candidates去重得到a
if(candidates［i］!=a.back())
a.push_back(candidates［i］);
}
n=a.size();
dfs(target,0);
return ans;
}
void dfs(int rt,int i) { //回溯算法
if(rt==0) {
ans.push_back(x);
}
else {
for (int j=i;j<n;j++) {
if(rt<a［j］) continue; //剪支
x.push_back(a［j］);
dfs(rt-a［j］,j);
x.pop_back();
}
}
}
};
上述程序提交后通过，执行用时为40ms，内存消耗为4.14MB。
5.4LintCode1915——举重★★★
问题描述: 奥利第一次来到健身房，她正在计算她能举起的最大重量。杠铃所能承受的最大重量为maxCapacity（1≤maxCapacity≤106），健身房里有n（1≤n≤42）个杠铃片，第i个杠铃片的重量为weights［i］（1≤weights［i］≤106）。奥利现在需要选一些杠铃片加到杠铃上，使得杠铃的重量最大，但是所选的杠铃片的重量总和又不能超过 maxCapacity，请计算杠铃的最大重量是多少。例如，n=3，weights={1，3，5}，maxCapacity=7，答案是6。要求设计如下成员函数:
int weightCapacity(vector<int> &weights,int maxCapacity) { }
解: 该问题与简单装载问题类似，用i遍历w（存放杠铃片的重量），tw表示当前选择的杠铃片的重量和，rw表示剩余杠铃片的重量和（w［i+1］+…+w［n-1］），左剪支是结束tw+w［i］>W的左分支的搜索，右剪支是结束tw+rw-w［i］≤ans的右分支的搜索，当到达叶子结点时将tw的最大值存放在ans中，搜索完毕返回ans即可。采用回溯法求解的程序如下:
class Solution {
int ans; //存放答案
vector<int> w; //存放杠铃片的重量
int W;
public:
int weightCapacity(vector<int> &weights,int maxCapacity) {
w=weights;
W=maxCapacity;
ans=0;
int rw=0;
for(int e:w) rw+=e;
dfs(0,rw,0);
return ans;
}
void dfs(int tw,int rw,int i) { //回溯算法
if(i>=w.size()) {
ans=max(ans,tw);
}
else {
if(tw+w［i］<=W)
dfs(tw+w［i］,rw-w［i］,i+1);
if(tw+rw-w［i］>ans)
dfs(tw,rw-w［i］,i+1);
}
}
};
上述程序提交后通过，执行用时为41ms，内存消耗为2.14MB。
5.5LintCode680——分割字符串★★
问题描述: 给定一个字符串s，设计一个算法可以选择在一个字符或两个相邻字符之后拆分字符串，使字符串仅由一个字符或两个字符组成，求所有可能的结果。例如，s="123"，答案是{{"1"，"2"，"3"}，{"12"，"3"}，{"1"，"23"}}。要求设计如下成员函数:
vector<vector<string>> splitString(string& s) { }
解: 采用回溯法求解，对于字符串s，用解向量x表示它的一个分割字符串，用i表示当前处理的字符的序号（i从0开始），对应的选择操作有两种，一是分割出s［i］，二是分割出s［i］s［i+1］，当i=n时得到一个分割字符串x，将其添加到答案ans中，最后返回ans即可。对应的程序如下:
class Solution {
vector<vector<string>> ans;
vector<string> x;
public:
vector<vector<string>> splitString(string& s) {
dfs(s,0);
return ans;
}
void dfs(string &s,int i) { //回溯算法
if(i>s.size()) return;
if(i==s.size()) ans.push_back(x);
else {
string str=s.substr(i,1);
x.push_back(str);
dfs(s,i+1);
x.pop_back();
str=s.substr(i,2);
x.push_back(str);
dfs(s,i+2);
x.pop_back();
}
}
};
上述程序提交后通过，执行用时为654ms，内存消耗为16.66MB。
5.6LintCode136——分割回文串★★
问题描述: 给定字符串s，设计一个算法将它分割成一些子串，使得每个子串都是回文串，返回所有可能的分割方案。不同方案之间的顺序可以是任意的。例如，s="aab"，答案是{{"aa"，"b"}，{"a"，"a"，"b"}}，注意单个字符构成的字符串是回文。要求设计如下成员函数:
vector<vector<string>> partition(string &s) { }
解: 利用《教程》中5.2.2节求幂集的解法2的思路进行分割。对应的回溯法程序如下:
class Solution {
vector<vector<string>> ans;
vector<string> x;
public:
vector<vector<string>> partition(string &s) {
if (s.empty()) return {};
dfs(s,0);
return ans;
}
void dfs(string& s,int i) { //回溯算法
if (i==s.size()) {
ans.push_back(x);
}
else {
for (int j=i;j<s.size();j++) {
string tmp=s.substr(i,j-i+1);
if (!isPali(tmp)) continue;
x.push_back(tmp);
dfs(s,j+1);
x.pop_back();
}
}
}
bool isPali(string& s) {
int i=0;
int j=s.size()-1;
while(i<j) {
if (s［i++］!=s［j--］) return false;
}
return true;
}
};
上述程序提交后通过，执行用时为553ms，内存消耗为5.59MB。
5.7LintCode816——旅行商问题★★★
问题描述: 给定n个城市，编号为1~n，城市之间的无向道路用三元组［A，B，C］表示，即城市 A和城市B之间有一条成本是 C的无向道路，全部道路用roads数组存放。设计一个算法求从城市1开始旅行所有城市的最小成本，一个城市只能通过一次，可以假设一定能够到达所有的城市。例如，n=3，roads={{1，2，1}，{2，3，2}，{1，3，3}}，答案是3，对应的最短路径为1>2>3。要求设计如下成员函数:
int minCost(int n,vector<vector<int>> &roads) { }
解: 为了简便，将n个城市的编号由1～n改为0～n-1，这样起点城市为0，题目是求从顶点0开始经过其他全部顶点并且每个顶点仅经过一次的最短路径长度。该问题与TSP问题类似，但有以下几点区别:
（1） 这里的路径不需要回到起点0。
（2） 图中两个顶点之间的道路是无向的，但两个顶点之间可能存在多条道路，应该取最小成本。
（3） 仅需要求最短路径长度，不必求一条最短路径。
采用基于排列树的回溯法对应的程序如下:
class Solution {
const int INF=0x3f3f3f3f;
vector<vector<int>> A;
int ans;
vector<int> x;
public:
int minCost(int n,vector<vector<int>> &roads) {
if(n==1) return 0;
A=vector<vector<int>>(n,vector<int>(n,INF));
for(int i=0;i<roads.size();i++) { //建立邻接表A
int a=roads［i］［0］-1;
int b=roads［i］［1］-1;
int w=roads［i］［2］;
A［a］［b］=min(A［a］［b］,w);
A［b］［a］=A［a］［b］;
}
x=vector<int>(n);
for(int i=0;i<n;i++) x［i］=i; //将0~n-1添加到x中
ans=INF;
int d=0;
dfs(d,n,1);
return ans;
}
void dfs(int d,int n,int i) { //回溯算法
if(i>=n) { //到达一个叶子结点
ans=min(ans,d);
}
else {
for(int j=i;j<n;j++) { //试探x［i］走到x［j］的分支
if (A［x［i-1］］［x［j］］!=INF) { //若x［i-1］到x［j］有边
if(d+A［x［i-1］］［x［j］］<ans) { //剪支
swap(x［i］,x［j］);
dfs(d+A［x［i-1］］［x［i］］,n,i+1);
swap(x［i］,x［j］);
}
}
}
}
}
};
上述程序提交后通过，执行用时为41ms，内存消耗为5.57MB。
5.8LeetCode784——字母大小写
全排列★★
问题描述: 给定一个含n（1≤n≤12）个字符的字符串s ，s中仅含小写字母、大写字母和数字，通过将字符串s中的每个字母转变大小写可以获得一个新的字符串，设计一个算法求可能得到的所有字符串集合，以任意顺序返回输出。例如，s ="a1b2"，答案是{"a1b2"，"a1B2"，"A1b2"，"A1B2"}。要求设计如下成员函数:
vector<string> letterCasePermutation(string s) { }
解: 用x表示解向量（一个可能得到的字符串），ans存放答案。首先置x为s。用i遍历x，分为两种情况:
（1） 若x［i］为数字，只有不转变一种选择。
（2） 若x［i］为字母，有不转变和转变两种选择。
当i=n时得到一个可能的字符串x，将其添加到ans中，最后返回ans即可。对应的程序如下:
class Solution {
vector<string> ans;
string x;
public:
vector<string> letterCasePermutation(string s) {
x=s;
dfs(0);
return ans;
}
void dfs(int i) { //回溯算法
if (i==x.size())
ans.push_back(x);
else {
dfs(i+1); //不转变
if (isalpha(x［i］)) { //s［i］是字母
x［i］ ^= 32; //大小写转换
dfs(i+1);
x［i］ ^= 32; //回溯(恢复)
}
}
}
};
上述程序提交后通过，执行用时为8ms，内存消耗为10.5MB。
5.9LeetCode1079——活字印刷★★
问题描述: 给定一个含n（1≤n≤7）个活字字模的 s，其中每个字模上都刻有一个字母 s［i］，设计一个算法求可以印出的非空字母序列的数目，注意每个活字字模只能使用一次。例如，s="AAB"，可能的序列为"A"、"B"、"AA"、"AB"、"BA"、"AAB"、"ABA"和"BAA"，答案为8。要求设计如下成员函数:
int numTilePossibilities(strings) { }
解法1: 用解向量x表示一个可以印出的非空字母序列，myset存放所有可以印出的非空字母序列，为了达到去重（例如，s="AA"时避免在可以印出的非空字母序列中出现两个"AA"）的目的，将myset设计为set<string>类型的容器，用数组used表示每个位置的字母是否使用过。与其他回溯算法不同的是，这里每一个非空的x都是一个解。对应的程序如下:
class Solution {
int ans=0;
vector<int> used;
set<string> myset; //用myset来去重
string x;
public:
int numTilePossibilities(string s) {
used=vector<int>(s.size(),0);
x="";
dfs(s);
return ans;
}
void dfs(string &s){ //回溯算法
if(x!="") {
if(myset.count(x)==0) {
myset.insert(x);
ans++;
}
}
for(int i=0;i<s.size();i++) {
if(used［i］==0){
x.push_back(s［i］);
used［i］=1;
dfs(s);
used［i］=0;
x.pop_back();
}
}
}
};
上述程序提交后通过，执行用时为116ms，内存消耗为14.9MB。
解法2: 题目不必求所有可以印出的非空字母序列，仅需要求数目ans（初始为0）。采用回溯法，假设直接在s上操作得到可以印出的非空字母序列，每次变动则递增一次ans。这样的关键是去重，这里采用对s排序的方法，用数组used表示每个位置的字母是否使用过，当处理字母s［i］时跳过(i>0 && s［i］==s［i-1］ && used［i-1］==0)的情况，从而保证原字符数组的前一个字符（例如'A'）永远放在后一个相同字符（例如'A'）的前面。对应的程序如下:
class Solution {
public:
int ans=0;
vector<int> used;
int numTilePossibilities(string s) {
used=vector<int>(s.size(),0);
sort(s.begin(),s.end());
dfs(s);
return ans;
}
void dfs(string &s){ //回溯算法
for (int i=0;i<s.size();i++) {
if (i>0 && s［i］==s［i-1］ && used［i-1］==0)
continue;
if(used［i］==0) {
used［i］=1;
ans++;
dfs(s);
used［i］=0;
}
}
}
};
上述程序提交后通过，执行用时为4ms，内存消耗为6MB。
5.10LeetCode93——复原IP地址★★
问题描述: 给定一个只包含数字的字符串s（0≤s.length≤3000，s仅由数字组成），用于表示一个IP地址，返回所有可能从s获得的有效IP地址，可以按任何顺序返回答案。有效IP地址正好由4个整数（每个整数位于0~255）组成，且不能含有前导零，整数之间用'.'分隔，如"0.1.2.201"和"192.168.1.1"是有效IP地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是无效IP地址。例如，s="010010"，结果为{"0.10.0.10"，"0.100.1.0"}。要求设计如下成员函数:
vector<string> restoreIpAddresses(string s) { }
解: 假设s中含n个数字符，用数组x存放一个IP地址的4个整数，用i遍历s（初始i=0对应解空间中的根结点），cnt累计找到的有效整数的个数。对于解空间中第i层的结点，考虑s［i］的决策，剩余的数字个数为n-i，若n-i>(4-cnt)×3，说明剩余的数字个数太多了，若n-i<4-cnt，说明剩余的数字个数太少了。如果cnt=4且i=n，说明找到一个解x，将x转换为IP字符串tmp添加到结果ans中。
在其他情况下，若遇到s［i］='0'，由于IP中的各个整数不能有前导零，那么这段IP地址只能为0; 否则扩展s［i..i+2］的每个位置j作为分割点，求出对应的整数d，若d有效则作为IP地址的一段，从j+1开始继续向下搜索，若d无效则返回。对应的程序如下:
class Solution {
vector<string> ans; //存放答案
int x［4］;
public:
vector<string> restoreIpAddresses(string s) {
dfs(s,0,0);
return ans;
}
void dfs(string& s,int cnt,int i) { //回溯算法
int n=s.size();
if(n-i>(4-cnt)*3) //找到4段IP 地址并且s遍历完
return;
if(n-i<(4-cnt))
return;
if (cnt==4 && i==n) {
string tmp="";
for(int j=0;j<4;j++) {
tmp+=to_string(x［j］);
if(j!=3) tmp+='.';
}
ans.push_back(tmp);
}
else {
if (s［i］=='0') { //不能有前导零,若当前为'0',则这段IP地址只能为0
x［cnt］=0;
dfs(s,cnt+1,i+1);
}
int d=0;
for (int j=i;j<min(i+3,n);j++) {
d=d*10+(s［j］-'0');
if (d>0 && d<=255) {
x［cnt］=d;
dfs(s,cnt+1,j+1);
}
else return; //d无效时回溯
}
}
}
};
上述程序提交后通过，执行用时为4ms，内存消耗为6.6MB。
5.11LeetCode22——括号的生成★★
问题描述: 给定一个整数n（1≤n≤8）表示要生成括号的对数，设计一个算法求生成的所有可能的并且有效的括号组合。例如，n=3，答案为{"((()))"，"(()())"，"(())()"，"()(())"，"()()()"}。要求设计如下成员函数:
vector<string> generateParenthesis(int n) { }
解: 用x表示当前解向量，从空串开始最多添加2n个括号，x［i］要么选择'('，要么选择')'，用left累计'('的个数，用right累计')'的个数。对于解空间中的某个结点，左分支对应选择'('，右分支对应选择')'，叶子结点是满足条件x.size()=2n的结点，若叶子结点同时满足left==n && right==n，则x是一个有效括号串，将其添加到ans中。采用的剪支操作是终止满足right > left || left>n || right>n条件的结点继续扩展。对应的回溯法程序如下:
class Solution {
vector<string>ans; //存放全部结果串
string x; //解向量(一个有效括号串)
public:
vector<string> generateParenthesis(int n) {
if(n==1)
ans.push_back("()");
else{
x="";
dfs(n,0,0);
}
return ans;
}
void dfs(int n,int left,int right) { //回溯算法
if (right>left || left>n || right>n)//剪支
return;
if (x.size()==n*2 && left==n && right==n) {
ans.push_back(x); //找到一个有效括号串,添加到ans中
}
else {
x.push_back('('); //选择'('
dfs(n,left+1,right);
x.pop_back(); //回溯
x.push_back(')'); //选择')'
dfs(n,left,right+1);
x.pop_back(); //回溯
}
}
};
上述程序提交后通过，执行用时为4ms，内存消耗为11.5MB。
5.12LeetCode89——格雷编码★★
问题描述: 格雷编码是一个二进制数字系统，n位格雷编码序列是一个由2n个整数组成的序列。
（1） 每个整数都在［0，2n-1］的范围内（含0和2n-1）。
（2） 第一个整数是0。
（3） 一个整数在序列中的出现不超过一次。
（4） 每对相邻整数的二进制表示恰好一位不同，且第一个和最后一个整数的二进制表示恰好一位不同。
给定一个整数n（1≤n≤16），设计一个算法求一个有效的n位格雷编码序列。例如，n=2时答案为{0，1，3，2}或者{0，2，3，1}，前者的二进制数是{00，01，11，10}，后者的二进制数是{00，10，11，01}。要求设计如下成员函数:
vector<int> grayCode(int n) { }
解: 用ans存放n位格雷编码序列，将g初始为0（n位格雷编码序列的第一个整数是0），也就是将g看成n位二进制数，二进制位0～二进制位n-1均为0，在此基础上做0/1翻转。例如，n=3时，3位格雷编码序列的产生过程如图5.1所示，答案为{0,1,3,7,5,2,6,4}。i对应g的二进制起始位，j从i到n-1位翻转，每一个结点值都是ans的一个元素，其顺序恰好是深度优先搜索顺序，最后返回ans即可。对应的程序如下:
class Solution {
vector<int> ans;
public:
vector<int> grayCode(int n) {
ans.push_back(0);
dfs(0,0,n);
return ans;
}
void dfs(int g,int i,int n) { //依次翻转g的第i到n-1位
if (i>=n) return;
for (int j=i;j<n;j++) {
int k=g^(1<<j); //翻转g的二进制位j得到k
ans.push_back(k);
dfs(k,j+1,n); //k自动回溯
}
}
};
上述程序提交后通过，执行用时为12ms，内存消耗为12.2MB。
图5.13位格雷编码序列的产生过程
5.13LeetCode301——删除无效的
括号★★★
问题描述: 给定一个由n（1≤n≤25）个括号和字母组成的字符串s，删除最小数量的无效括号，使得输入的字符串有效，设计一个算法求所有可能的结果，答案可以按任意顺序返回。例如，s="(a)())()"，答案是{"(a())()"，"(a)()()"}。要求设计如下成员函数:
vector<string> removeInvalidParentheses(string s) { }
解: 若一个字符串中的括号匹配，必须满足两点，一是任意前缀中右括号的个数不少于左括号的个数，二是总的左、右括号个数相同。采用回溯法求解。首先通过遍历s求出剩余左、右括号的个数left和right（初始均为0），其过程是在遍历中遇到左括号时left增1，遇到右括号时如果left≠0则将right减1，否则right增1。
再尝试遍历所有可能的去掉非法括号的方案，即尝试在原字符串s中去掉left个左括号和right个右括号，然后检测剩余的字符串是否为合法匹配，如果是合法匹配，则得到一个可能的结果。需要注意的是，这样得到的结果字符串可能存在重复，可以利用哈希集合实现去重。对应的程序如下:
class Solution {
public:
set<string> ans; //存放结果字符串
vector<string> removeInvalidParentheses(string s) {
int left=0;
int right=0;
for(int i=0;i<s.size();i++) {
if (s［i］=='(') left++;
else if (s［i］==')') {
if (left==0) right++;
else left--;
}
}
dfs(s,0,left,right);
vector<string> anss;
for(auto e:ans) anss.push_back(e);
return anss;
}
void dfs(string s,int i,int left,int right) { //回溯算法
if (left==0 && right==0) {
if (valid(s)) ans.insert(s); //自动去重
}
else {
for (int j=i;j<s.size();j++) {
if (left+right>s.size()-j) return; //剪支
if (left>0 && s［j］=='(') //尝试去掉一个左括号
dfs(s.substr(0,j)+s.substr(j+1),j,left-1,right);
if (right>0 && s［j］==')') //尝试去掉一个右括号
dfs(s.substr(0,j)+s.substr(j+1),j,left,right-1);
}
}
}
bool valid(string& s) { //判断s中的括号是否匹配
int cnt=0;
for (int i=0;i<s.size();i++) {
if (s［i］=='(') cnt++;
else if(s［i］==')') {
cnt--;
if (cnt<0) return false;
}
}
return cnt==0;
}
};
上述程序提交后通过，执行用时为36ms，内存消耗为8.3MB。可以改为这样去重，在每次进行搜索时，如果遇到连续相同的括号只需要搜索一次即可。例如当前遇到的字符串为"(((())"，去掉前4个左括号中的任意一个生成的结果字符串是一样的，均为"((())"，因此在这样的情况下只需要去掉一个左括号后进入下一轮搜索，不需要将前4个左括号都尝试一遍。对应的程序如下:
class Solution {
public:
vector<string> ans; //存放答案
vector<string> removeInvalidParentheses(string s) {
int left=0;
int right=0;
for(int i=0;i<s.size();i++) {
if (s［i］=='(') left++;
else if (s［i］==')') {
if (left==0) right++;
else left--;
}
}
dfs(s,0,left,right);
return ans;
}
void dfs(string s,int i,int left,int right) { //回溯算法
if (left==0 && right==0) {
if (valid(s))
ans.push_back(s);
}
else {
for (int j=i;j<s.size();j++) {
if (j>i && s［j］==s［j-1］) //去重
continue;
if (left+right>s.size()-j) //剪支
return;
if (left>0 && s［j］=='(') //尝试去掉一个左括号
dfs(s.substr(0,j)+s.substr(j+1),j,left-1,right);
if (right>0 && s［j］==')') //尝试去掉一个右括号
dfs(s.substr(0,j)+s.substr(j+1),j,left,right-1);
}
}
}
bool valid(string& s) { //判断s中的括号是否匹配
int cnt=0;
for (int i=0;i<s.size();i++) {
if (s［i］=='(') cnt++;
else if(s［i］==')') {
cnt--;
if (cnt<0) return false;
}
}
return cnt==0;
}
};
上述程序提交后通过，执行用时为4ms，内存消耗为7.4MB。
5.14POJ3050——跳房子
时间限制: 1000ms，空间限制: 65536KB。
问题描述: 奶牛玩跳房子游戏，不是要跳入一组线性编号的方格，而是跳入一个5×5的网格，其中每个方格有一个数字。奶牛熟练地跳到网格中的任何数字上，并向前、向后、向右或向左（不能斜向）跳到网格中的另一个数字，这样跳过6个方格，这些方格的数字合并起来得到一个6位数的整数（可能有前导零，例如000201）。求可以用这种方式创建的不同整数的数量。
输入格式: 共5行，每行5个整数表示一个网格。
输出格式: 输出可以创建的不同整数的数量。
输入样例:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
输出样例:
15
解: 网格中的每个方格最多有上、下、左、右相邻方格，从网格中的每个位置出发搜索，走5步得到一个整数，将其添加到ans中，由于添加的整数可能重复，需要去重，为此将ans设计为set容器。对应的程序如下:
#include<iostream>
#include<set>
using namespace std;
int a［5］［5］;
set<int> ans; //存放结果整数
int dx［4］={-1, 1, 0, 0};
int dy［4］={0, 0, -1, 1};
void dfs(int x,int y,int k,int d) { //回溯算法
if(k==6) {
ans.insert(d);
}
else {
for(int i=0;i<4;i++) {
int nx=x+dx［i］;
int ny=y+dy［i］;
if(nx>=0 && nx<5 && ny>=0 && ny<5) {
k++;
d=d*10+a［nx］［ny］;
dfs(nx,ny,k,d);
d=(d-a［nx］［ny］)/10; //回溯
k--;
}
}
}
}
int main() {
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++)
scanf("%d", &a［i］［j］);
}
for(int i=0;i<5;i++) { //将每个位置作为起点试探
for(int j=0;j<5;j++)
dfs(i,j,1,a［i］［j］);
}
printf("%d＼n", ans.size());
return 0;
}
上述程序提交后通过，执行用时为32ms，内存消耗为448KB。
5.15POJ1724——道路
时间限制: 1000ms，空间限制: 65536KB。
问题描述: 编号为1～N的N个城市之间通过单向道路相连，每条道路都有两个与之相关的参数，即道路长度和过路费。现在Bob在城市1，Alice在城市N，Bob有K元钱，请帮助Bob选择可以找到Alice并且能够负担的最短路径。
输入格式: 输入的第一行包含整数K（0≤K≤10000），第二行包含整数N（2≤N≤100），表示城市总数，第三行包含整数R（1≤R≤10000），表示道路总数。以下R行中的每一行由单个空格分隔的整数S、D、L和T来表示一条道路，其中S是源城市（1≤S≤N），D是目的地城市（1≤D≤N），L是道路长度（1≤L≤100），T是过路费（0≤T≤100），注意不同的道路可能具有相同的源城市和目的地城市。
输出格式: 输出一行，包含从城市1到城市N的最短路径的总长度，其总费用小于或等于K。如果这样的路径不存在，则输出-1。
输入样例:
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
输出样例:
11
解: 由输入数据建立图的邻接表存储结构，用ans存放答案（初始为∞）。从顶点1开始搜索，curlen和curcost分别表示从顶点1到达当前顶点s的最短路径长度和费用，找到顶点s的相邻顶点v，若顶点v已经访问，或者curcost+<s，v>边的费用>K或者curlen+<s，v>边长度>=ans时均跳过顶点v的试探，否则从顶点v出发继续搜索，当s=N时说明找到了一条从顶点1到达顶点N的路径，置ans=min(ans，curlen)。最后返回ans即可。对应的回溯算法如下:
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;
struct Edge { //边类型
int v;
int len;
int cost;
int next;
};
int head［MAXN］; //图的邻接表
Edge edg［100*MAXN］;
int cnt;
int K,N,R;
int visited［MAXN］;
int ans; //存放答案
int curlen,curcost;
void addedge(int S,int D,int L,int T) { //增加一条边
edg［cnt］.v=D;
edg［cnt］.len=L;
edg［cnt］.cost=T;
edg［cnt］.next=head［S］;
head［S］=cnt++;
}
void dfs(int s) { //回溯算法
if(s==N) {
ans=min(ans,curlen); //更新步数最小值
}
else {
for(int j=head［s］;j!=-1;j=edg［j］.next) {
int v=edg［j］.v;
int len=edg［j］.len;
int cost=edg［j］.cost;
if(visited［v］==1) continue;
if(curcost+cost>K) continue; //总费用剪支
if(curlen+len>=ans) continue; //路径长度剪支
curlen+=len;
curcost+=cost;
visited［v］=1;
dfs(v);
visited［v］=0;
curcost-=cost;
curlen-=len;
}
}
}
int main() {
scanf("%d%d%d",&K,&N,&R);
int S,D,L,T;
memset(head,0xff,sizeof(head));
cnt=0;
for(int i=0;i<R;i++) {
scanf("%d%d%d%d",&S,&D,&L,&T);
addedge(S,D,L,T);
}
memset(visited,0,sizeof(visited));
ans=INF;
curlen=0; curcost=0;
dfs(1);
if(ans==INF)
printf("-1＼n");
else
printf("%d＼n",ans);
return 0;
}
上述程序提交后通过，执行用时为63ms，内存消耗为272KB。
5.16POJ1699——最佳序列
时间限制: 1000ms，空间限制: 10000KB。
问题描述: 基因是由DNA组成的，组成DNA的核苷酸碱基是A（腺嘌呤）、C（胞嘧啶）、G（鸟嘌呤）和 T（胸腺嘧啶）。给定一个基因的几个片段，要求从它们构造一个最短序列，该序列应使用所有段，并且不能翻转任何片段。
例如，给定"TCGG"、"GCAG"、"CCGC"、"GATC"和"ATCG"，可以采用如图5.2所示的方式滑动基因片段构造出一个长度为11的序列，
图5.2构造最短序列的过程
它是最短序列（但可能不是唯一的）。
输入格式: 第一行是一个整数T（1≤T≤20），表示测试用例的数量。然后是T个测试用例。每个测试用例的第一行包含一个整数n（1≤n≤10），它表示基因片段的数量，下面的n行分别表示n个基因片段，假设基因片段的长度为1~20。
输出格式: 对于每个测试用例，输出一行包含可以从这些基因片段构造的最短序列的长度。
输入样例:
1
5
TCGG
GCAG
CCGC
GATC
ATCG
输出样例:
11
解法1: 题目是求n个基因片段去掉最大相同前、后缀重叠部分后得到的字符串的最小长度。用ans存放答案，字符串数组gen存放n个基因片段，glen数组存放n个基因片段的长度，设计二维数组addlen，其中addlen［i］［j］表示基因片段i合并基因片段j（去掉基因片段i的后缀和基因片段j的前缀的最大重叠部分）得到的字符串相对基因片段i增加的长度。例如，gen［i］="TCGG"，gen［j］="GCAG"，前者的后缀和后者的前缀的最大相同部分是"G"，两者合并后为"TCGGCAG"，是在gen［i］的基础上增加了3个字符，所以addlen［i］［j］=3，注意addlen数组不是对称的。
采用基于子集树框架的回溯算法，从每个基因开始搜索，通过比较得到合并基因序列，求出最小长度ans并且输出。对应的程序如下:
#include<iostream>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3;
char gen［11］［21］;
int glen［11］;
int addlen［11］［11］;
int ans;
int used［11］;
int n;
void dfs(int pre,int curlen,int step) { //回溯算法(子集树)
if(curlen>=ans) //剪支
return;
if(step==n) {
ans=min(ans,curlen);
}
else {
for(int j=0;j<n;j++) {
if(used［j］==0) {
used［j］=1;
dfs(j,curlen+addlen［pre］［j］,step+1);
used［j］=0;
}
}
}
}
void add(int x,int y) { //求addlen数组
int length=0;
for(int i=1;i<=glen［x］ && i<=glen［y］;i++) {
bool flag=true;
for(int j=glen［x］-i,k=0;k<i;k++,j++) {
if(gen［x］［j］!=gen［y］［k］) {
flag=false;
break;
}
}
if(flag) length=i;
}
addlen［x］［y］=glen［y］-length;
}
int main() {
int T;
cin >> T;
while(T--) {
cin >> n;
for(int i=0;i<n;i++) {
cin >>gen［i］;
glen［i］=strlen(gen［i］);
used［i］=0;
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i!=j) add(i,j);
}
}
ans=INF;
for(int i=0;i<n;i++) { //从每个基因片段i开始求解
memset(used,0,sizeof(used));
used［i］=1;
dfs(i,glen［i］,1);
used［i］=0;
}
cout << ans << endl;
}
return 0;
}
上述程序提交后通过，执行用时为47ms，内存消耗为172KB。
解法2: n个基因片段的编号为0～n-1，将每个基因看成一个顶点，addlen［i］［j］表示顶点i到顶点j的权值，这样构成一个带权有向图，求经过全部顶点的最短路径的长度（路径的首结点值为该基因片段的长度）。类似于TSP问题，采用基于排列树框架的回溯法程序如下:
#include<iostream>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3;
char gen［11］［21］;
int glen［11］;
int addlen［11］［11］;
int ans;
int n;
int x［11］; //解向量
void dfs(int curlen,int i) { //回溯算法(排列树)
if (i>=n) { //到达一个叶子结点
ans=min(ans,curlen);
}
else {
for (int j=i;j<n;j++) {
swap(x［i］,x［j］); //交换x［i］与x［j］
if(i==0) {
dfs(glen［x［0］］,i+1);
}
else if(curlen+addlen［x［i-1］］［x［i］］<=ans) { //剪支
dfs(curlen+addlen［x［i-1］］［x［i］］,i+1);
}
swap(x［i］,x［j］); //交换x［i］与x［j］：恢复
}
}
}
void add(int x,int y) { //求addlen数组
int length=0;
for(int i=1;i<=glen［x］ && i<=glen［y］;i++) {
bool flag=true;
for(int j=glen［x］-i,k=0;k<i;k++,j++) {
if(gen［x］［j］!=gen［y］［k］) {
flag=false;
break;
}
}
if(flag) length=i;
}
addlen［x］［y］=glen［y］-length;
}
int main() {
int T;
cin >> T;
while(T--) {
cin >> n;
for(int i=0;i<n;i++) {
cin >>gen［i］;
glen［i］=strlen(gen［i］);
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++)
if(i!=j) add(i,j);
}
for(int i=0;i<n;i++)
x［i］=i;
ans=INF;
dfs(0,0);
cout << ans << endl;
}
return 0;
}
上述程序提交后通过，执行用时为32ms，内存消耗为172KB。
5.17POJ1564——求和
时间限制: 1000ms，空间限制: 10000KB。
问题描述: 给定一个指定的总和t和一个包含n个整数的序列，求该序列中加起来和为t的不同子序列的个数。例如，t=4，n=6，序列为{4，3，2，2，1，1}，则有4个不同子序列之和等于4，即4、3+1、2+2和2+1+1。一个整数在序列中出现的次数可以与它在子序列中出现的次数一样多，并且单个数字算作总和。
输入格式: 输入包含一个或多个测试用例，每行一个测试用例，每个测试用例包含t（总数），后跟n（序列中的整数个数），然后是n个整数x1、……、xn。如果n=0，则表示输入结束。否则，t为小于1000的正整数，n为1~12（含）的整数，x1、……、xn是小于100的正整数，所有整数之间由一个空格分隔。每个序列中的整数以非递增顺序出现，并且可能有重复。
输出格式: 对于每个测试用例，首先输出一行包含"Sums of"、总数和一个冒号，然后每行输出一个和式子，如果没有（总数为0）则输出"NONE"的行。每个和式子中的数字必须以非递增顺序出现，一个整数在和式子中的重复次数可能与在原始序列中的重复次数一样多，和式子本身必须根据出现的整数按降序排序，换句话说，和式子必须按其第一个整数排序，具有相同第一个整数的和式子必须按其第二个整数排序，以此类推。在每个测试用例中，所有的和式子必须是不同的。
输入样例:
4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
输出样例:
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
解法1: 对于每个测试用例，用ans存放答案，其中每个元素为vector<int>类型，存放一个和为t的子序列，由于最后的结果需要去重，所以将ans设计为set容器，set中默认是递增排列，题目要求每个和式子中的整数必须以非递增顺序出现，所以得到ans后反向输出ans中的各个和式子即可。求和式子的过程与求幂集类似，用x作为解向量，解空间中根结点对应i=0，当i=n时判断当前子序列和cursum=t是否成立，若成立将x添加到ans中。对应的回溯法程序如下:
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int t,n;
int a［20］;
set<vector<int>> ans;
vector<int> x; //解向量
void dfs(int cursum,int i) { //回溯算法
if(i>=n) { //到达一个叶子结点
if(cursum==t) ans.insert(x);
}
else {
if(cursum+a［i］<=t) { //左剪支
x.push_back(a［i］);
dfs(cursum+a［i］,i+1);
x.pop_back();
}
dfs(cursum,i+1); //不选择a［i］
}
}
int main() {
while(scanf("%d%d",&t,&n)!=EOF) {
if(!n) break;
for(int i=0;i<n;i++)
scanf("%d",&a［i］);
ans.clear();
printf("Sums of %d:＼n",t);
dfs(0,0);
if(ans.size()==0)
printf("NONE＼n");
else {
set<vector<int>>::reverse_iterator rit;
for(rit=ans.rbegin();rit!=ans.rend();rit++) {
vector<int> e=*rit;
for(int i=0;i<e.size();i++) {
if(i!=0) printf("+");
printf("%d",e［i］);
}
printf("＼n");
}
}
}
}
上述程序提交后通过，执行用时为0ms，内存消耗为128KB。
解法2: 定义大问题f(cursum，i)是选择a［i］后（cursum=a［i］）在a［i+1..n-1］中选择若干整数得到所有以a［i］开头的和为t的子序列。求解过程是对于i+1～n-1内的整数j，当cursum+a［j］≤t时，小问题是f(cursum+a［j］，j)。递归出口是i≥n或者cursum=t。例如，t=7，n=5，a［］={4，3，2，1，1}，调用dfs(4，0)和dfs(3，1)的过程如图5.3所示，得到4个解，其他调用没有解，这样的4个解中有两个存放，去重的结果是4+3、4+2+1和3+2+1+1。在求解向量x时需要回溯。
图5.3调用dfs(4，0)和dfs(3，1)的过程
对应的回溯法程序如下:
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int t,n;
int a［20］;
set<vector<int>> ans;
vector<int> x; //解向量
void dfs(int cursum,int i) { //回溯算法
if(i>=n) return;
if(cursum==t) {
ans.insert(x);
}
else {
for(int j=i+1;j<n;j++){
if(cursum+a［j］<=t) {
x.push_back(a［j］);
dfs(cursum+a［j］,j);
x.pop_back();
}
}
}
}
int main() {
while(scanf("%d%d",&t,&n)!=EOF) {
if(!n) break;
for(int i=0;i<n;i++)
scanf("%d",&a［i］);
ans.clear();
printf("Sums of %d:＼n",t);
for(int i=0;i<n;i++) {
x.clear();
x.push_back(a［i］);
dfs(a［i］,i);
}
if(ans.size()==0)
printf("NONE＼n");
else {
set<vector<int>>::reverse_iterator rit;
for(rit=ans.rbegin();rit!=ans.rend();rit++) {
vector<int> e=*rit;
for(int i=0;i<e.size();i++) {
if(i!=0) printf("+");
printf("%d",e［i］);
}
printf("＼n");
}
}
}
}
上述程序提交后通过，执行用时为0ms，内存消耗为128KB。
5.18POJ2245——组合
时间限制: 1000ms，空间限制: 65536KB。
问题描述: 给定由k个整数构成的集合S，求其中所有6个整数的集合。
输入格式: 输入包含一个或多个测试用例，每个测试用例由一行组成，其中包含多个用空格隔开的整数，第一个整数是k（6<k<13），然后k个整数指定集合S，按照升序排列。输入以k=0终止。
输出格式: 对于每个测试用例，输出S中所有6个整数的组合，每个组合按升序排列，全部的组合按字典序输出，每个测试用例输出后空一行，最后一个测试用例之后不空行。
输入样例:
7 1 2 3 4 5 6 7
0
输出样例:
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
解: 用a存放输入的k个整数，设计回溯算法dfs(cnt，i)表示从a［i］开始选择6个整数，用ans存放选择的整数。当cnt=6时输出ans。对应的程序如下:
#include<iostream>
using namespace std;
const int MAXN=14;
int a［MAXN］,ans［6］;
int k;
void dfs(int cnt,int i) { //回溯算法
if(cnt==6) { //已经组合了6个数就输出
printf("%d",ans［0］);
for(int j=1;j<6;j++)
printf(" %d",ans［j］);
printf("＼n");
}
else {
for(int j=i;j<k;j++) {
ans［cnt］=a［j］;
dfs(cnt+1,j+1);
}
}
}
int main() {
bool first=true;
while(scanf("%d",&k)!=EOF && k) {
for(int i=0;i<k;i++)
scanf("%d",&a［i］);
if(!first)
printf("＼n"); //第一个测试之前不加空行,其他加空行
first=false;
dfs(0,0);
}
return 0;
}
上述程序提交后通过，执行用时为16ms，内存消耗为88KB。
5.19POJ1321——棋盘问题
时间限制: 1000ms，空间限制: 10000KB。
问题描述: 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别，要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入格式: 输入含有多组测试数据。每组数据的第一行是两个正整数n和k（n≤8，k≤n），用一个空格隔开，表示将在一个n×n的矩阵内描述棋盘，以及摆放棋子的数目。当输入为-1 -1时表示输入结束，随后的n行描述了棋盘的形状: 每行有n个字符，其中'#'表示棋盘区域，'.'表示空白区域（数据保证不出现多余的空白行或者空白列）。
输出格式: 对于每组测试数据，给出一行输出，输出摆放的方案数目C（数据保证C<231）。
输入样例:
2 1
# .
. #
4 4
... #
.. # .
. # ..
# ...
-1 -1
输出样例:
2
1
解: 简化的皇后问题，采用回溯法求解，用二维数组map存放棋盘，used数组中的used［j］表示第j列是否已经放过棋子。对应的程序如下:
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 10
using namespace std;
char map［MAXN］［MAXN］;
bool used［MAXN］; //记录一列是否已经放过棋子
int n,k,ans;
void dfs(int i,int num) { //回溯算法
if (num==k) { //找到一个解ans增1
ans++;
}
else if(i<n) {
for (int j=0;j<n;j++) { //搜索行i的每个列j
if (map［i］［j］=='#' && used［j］==false) {
used［j］=true;
dfs(i+1,num+1); //在行i的列j放置一个棋子
used［j］=false;
}
}
dfs(i+1,num); //行i不放置任何棋子
}
}
int main() {
while(scanf("%d%d",&n,&k)) {
if (n==-1 && k==-1) break;
for(int i=0;i<n;i++)
scanf(" %s",map［i］);
memset(used,false,sizeof(used));
ans=0;
dfs(0,0);
printf("%d＼n",ans);
}
return 0;
}
上述程序提交后通过，执行用时为47ms，内存消耗为88KB。
5.20POJ2488——骑士之旅
时间限制: 1000ms，空间限制: 65536KB。
问题描述: 骑士想要周游世界，可以将这个世界看成p列q行的棋盘，骑士只能向8个方向走“日”字，而且不能重复。问骑士可以在棋盘的任何方格上开始和结束吗？
输入格式: 输入的第一行包含一个正整数n，表示有n个测试用例。每个测试用例输入一行，包含两个正整数p和q，表示一个p×q 棋盘（1≤p×q≤26）。
输出格式: 每个测试用例的输出以"Scenario #i: "开始，其中i是从1开始的测试用例编号，这里的路径是一条从起始位置经过棋盘中全部方格的路径，路径中的每个方格用“行字母+列数字”表示，行字母为以"A"开始的q个字母，列数字是1～p，这样每条路径用一个序列表示，本题求一条按字典序排列最小的路径，如果不存在这样的路径，则输出"impossible"。每个测试用例输出之后空一行，最后一个测试用例的后面不空行。
输入样例:
3
1 1
2 3
4 3
输出样例:
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
解: 题目中第3个测试用例的图示如图5.4所示，即棋盘的行号为'A'～'C'、列号为1～4。从任意一个位置出发经过棋盘中全部方格的路径
图5.4第3个测试用例
的图示
可能有多条，这些路径按题目规定的路径表示，即路径序列也不同，答案是一条按字典序排列最小的路径。
对于p列q行的棋盘，行号为'A'～'A'+q-1、列号为1～p。为了保证找到的路径是按字典序排列最小的路径，必须从（A，1）位置开始搜索，另外，由于每个位置最多有8个相邻位置，所以搜索次序也应该遵循字典序，(x，y)位置的8个相邻位置如图5.5所示，按字典序建立的偏移量数组如下:
int dx［8］={-2，-2，-1，-1，1，1，2，2};
int dy［8］={-1，1，-2，2，-2，2，-1，1};
图5.5(x，y)位置的8个相邻位置
可以看成(x，y)位置的8个方位，在搜索时di依次从0到7试探。用path数组存放找到的第一条路径，step表示路径长度或者path数组的下标，当step=p*q时path即为所求，置flag=true结束搜索过程。如果搜索完毕flag仍然为false，则说明找不到按字典序排列最小的路径（注意并不表示找不到其他路径）。对应的程序如下:
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=30;
int visited［MAXN］［MAXN］;
int p,q;
int dx［8］={-2,-2, -1,-1, 1, 1, 2, 2};
int dy［8］={-1, 1, -2, 2,-2, 2,-1, 1};
struct Path {
int x,y;
} path［MAXN］;
bool flag;
void dfs(int x,int y,int step) { //回溯算法
if(flag) return;
path［step］.x=x;
path［step］.y=y;
if(step==p*q) {
flag=true;
}
else {
for(int di=0;di<8;di++) {
int nx=x+dx［di］;
int ny=y+dy［di］;
if(nx>=1 && nx<=q && ny>=1 && ny<=p && !visited［nx］［ny］) {
visited［nx］［ny］=1;
dfs(nx,ny,step+1);
visited［nx］［ny］=0;
}
}
}
}
int main() {
int t;
cin >> t;
for(int cas=1;cas<=t;cas++) {
cin >> p >> q;
memset(visited,0,sizeof(visited));
flag=false;
int x=1,y=1,step=1;
visited［x］［y］=1;
dfs(x,y,step);
cout << "Scenario #" << cas<<":" << endl;
if(flag) {
for(int i=1;i<=p*q;i++) {
cout << char(path［i］.x-1+'A') << path［i］.y;
}
cout << endl;
}
else cout << "impossible" << endl;
if(cas!=t) cout << endl;
}
return 0;
}
上述程序提交后通过，执行用时为16ms，内存消耗为180KB。