C1927 八皇后(深度优先搜索dfs)
程序员文章站
2022-06-11 12:26:01
...
题目链接:https://www.cometoj.com/problem/1927
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
vector<string> str;
int vis[9][9];
int jump[4][2] = {{1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
bool isRight(int x, int y) //判断是否在8 * 8表格中
{
if(x >= 1 && x <= 8)
if(y >= 1 && y <= 8)
return true;
return false;
}
void mark(int x, int y) //标记
{
for (int i = 1; i <= 8; i++)
vis[x][i]++, vis[i][y]++;
vis[x][y]--;
int x1, y1;
for (int i = 0; i < 4; i++)
for (int j = 1; j < 8; j++)
{
x1 = x + jump[i][0] * j;
y1 = y + jump[i][1] * j;
if(isRight(x1, y1))
vis[x1][y1]++;
else
break;
}
}
void remark(int x, int y) //逆标记
{
for (int i = 1; i <= 8; i++)
vis[x][i]--, vis[i][y]--;
vis[x][y]++;
int x1, y1;
for (int i = 0; i < 4; i++)
for (int j = 1; j < 8; j++)
{
x1 = x + jump[i][0] * j;
y1 = y + jump[i][1] * j;
if (isRight(x1, y1))
vis[x1][y1]--;
else
break;
}
}
void Copy(vector<int> vv) //输出
{
string ss;
for (int i = 0; i < vv.size(); i++)
ss.push_back('0' + vv[i]);
str.push_back(ss);
}
void dfs(int y)
{
if(y == 9)
{
Copy(v);
return;
}
for (int i = 1; i <= 8; i++)
if(!vis[i][y])
{
v.push_back(i);
mark(i, y);
dfs(y + 1);
remark(i, y); //回溯
v.pop_back();
}
}
int main()
{
int n, k;
cin >> n;
dfs(1); //得到八皇后表
while (n--)
{
cin >> k;
cout << str[k - 1] << endl;
}
return 0;
}
推荐阅读
-
DFS(一):深度优先搜索的基本思想
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
数据结构与算法-----BFS与DFS(广度优先搜索与深度优先搜索)
-
数据结构与算法_深度优先搜索(DFS)与广度优先搜索(BFS)详解
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
BFS(广度优先搜索算法)和DFS(深度优先搜索算法)
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
【算法】广度优先搜索(BFS)和深度优先搜索(DFS)
-
图 - DFS深度优先搜索和BFS广度优先搜索