1.要说八皇后问题，具体问题就不在描述了
第一种：用矩阵存储棋盘map[n][n]：一行一行（或一列一列）放棋子。
代码如下
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int map[20][20];
int cnt = 0;
int n;
bool check(int x, int y)
{
for(int i = 0; i < n; i++)
{
if(map[x][i]) return false;//判断行
if(map[i][y]) return false;//判断列
}
for(int i = 0; i < n; i++)//判断斜列
{
for(int j = 0; j < n; j++)
{
if(abs(i-x) == abs(j-y))
if(map[i][j])
return false;
}
}
//都没有问题
return true;
}
//打印map
void print_map()
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << map[i][j] << " ";
cout << endl;
}
cout << endl;
}
void dfs(int col)//最开始传入0， 表示第一列
{
for(int i = 0; i < n; i++)
{
if(check(i, col))// 第一列看看有没有那个点可以放皇后
{
if(col == n-1) //表示最后一列，皇后放置完毕
{
map[i][col] = 1; //放皇后
print_map(); //打印map
cnt++; //记录解的个数
map[i][col] = 0; //恢复
}
else
{
map[i][col] = 1; //放皇后
dfs(co+1); //进入下一列
map[i][col] = 0; //恢复
}
}
}
}
int main()
{
memset(map, 0, sizeof(map));
cin >> n;
dfs(0);
cout << cnt;
}
回溯最重要的是每次要恢复已经放置的皇后。
缺点：每个点都去check，意味着每个点都要去遍历整张map，太慢，所以有了第二种。
第二种：用一个map[n][n]存储棋盘，四个数组表示（棋盘每个位置的行，列， 斜向左列， 斜向右列）有没有放置皇后，虽然不直观，多了四个一维数组，但是高效。
代码如下：
#include<bits/stdc++.h>
using namespace std;
bool row[100+5], col[100+5], lef[100+5], rig[100+5]; //分别为行，列， 斜向左列和斜向右列
bool chess[20][20];
int n, k = 0;
void print_answer()
{
//print省略
k++;
}
void dfs(int ro) //从第一行开始
{
for(int i = 0; i < n; i++)
{ //给出一个点
if(!row[ro] && !col[i] && !lef[ro+i] && !rig[i-ro+n]) //如果这个点所在的行，列，斜向左列，斜向右列都没有其他皇后
{
row[ro] = true;
col[i] = true;
lef[ro+i] = true;
rig[i-ro+n] = true;
chess[ro][i] = true; //放置皇后
if(ro == n-1)
print_answer();
else dfs(ro+1);
row[ro] = false;
col[i] = false;
lef[ro+i] = false;
rig[i-ro+n] = false;
chess[ro][i] = false; // 恢复皇后
}
}
}
int main()
{
memset(row, false, sizeof(row));
memset(col, false, sizeof(col));
memset(lef, false, sizeof(lef));
memset(rig, false, sizeof(rig));
cin >> n;
dfs(0);
cout << k;
return 0;
}
由于每次查找check都是O(1)，自然而然高效率了。
2.单词方阵：题目描述
给一n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：
输入：
8 输出：
qyizhong *yizhong
gydthkjy gy******
nwidghji n*i*****
orbzsfgz o**z****
hhgrhwth h***h***
zzzzzozo z****o**
iwdfrgng i*****n*
yyyygggg y******g
思路：遍历方阵，找到首字母'y'，进入深搜模式，深搜分两个模块：第一是向八个方向找，找到下一个字母'i'。第二个模块是已经找到第二个字母，即确定了方向，然后向确定的方向深搜。
由于在查找完整单词的过程中需要标记单词位置，即边查找便标记（为了输出），查找到了完整的单词还不能抹掉（因为抹掉就不能输出了）。 就会产生一个问题：单词查找了一半发现错误，怎么把之前已经标记了的位置抹掉？ 这里有一个新的技巧就是：深搜函数使用bool类型，只有这一整个单词查找成功，这个单词每个字母的所在位置才标记，即：
if(dfs(next_letter)) return true;
但是在深搜的第一个模块却不能直接return true。 因为要尝试8个方向，如果一个方向查到到了，就直接return true了，就会漏掉剩下的情况。因此，不妨在函数开始初始化一个bool类型的标记，如下：
bool dfs(char letter)
{
bool ok = false;
......
if(dfs(next_letter) ok = true;
......
return ok;
}
就可以完美解决问题。奉上代码：
#include<bits/stdc++.h>
using namespace std;
int n;
char num[100+5][100+5];
bool have[100+5][100+5];
string s = "yizhong";
bool dfs(int i, int x, int y, int d1, int d2) //参数分别是字母下标(用s[i])得到该字母，开始深搜的开始位置x, y； 以及第二模块中确定的方向d1, d2
{
bool ok = false;
if(i == 7) return true;
if(i == 1) //第一模块，找下一字母，确定方向
for(int k1 = -1; k1 <= 1; k1++)
for(int k2 = -1; k2 <= 1; k2++)
{
if(!k1 && !k2) continue;
int x1 = x + k1, y1 = y + k2;
if(x1 >= 0 && x1 < n && y1 >= 0 && y1 < n)
{
if(num[x1][y1] == s[i])
{
if(dfs(i+1, x1, y1, k1, k2)) 如过深搜链查找完成，全部return ok，标记改单词的所有字母的位置
{
have[x1][y1] = true;
ok = true;
}
}
}
}
else //第二模块，按照确定方向找下一个字母
{
int x1 = x+d1, y1 = y+d2;
if(x1 >= 0 && x1 < n && y1 >= 0 && y1 < n)
if(num[x1][y1] == s[i])
{
if(dfs(i+1, x1, y1, d1, d2))
{
have[x1][y1] = true;
return true;
}
}
}
return ok;
}
int main()
{
memset(have, false, sizeof(have));
cin >> n;
for(int i = 0; i < n; i++)
scanf("%s", num[i]);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(num[i][j] == 'y') //开始深搜
{
if(dfs(1, i, j, 0, 0)) have[i][j] = true;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
if(have[i][j]) cout << num[i][j];
else cout << "*";
cout << endl;
}
}
网友评论