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;
}
}
网友评论