欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C1927 八皇后(深度优先搜索dfs)

程序员文章站 2022-06-11 12:26:01
...

题目链接:https://www.cometoj.com/problem/1927
C1927 八皇后(深度优先搜索dfs)

#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;
}

相关标签: Comet OJ