头像

活泼的派大星




离线:9天前



P1219 八皇后,输出字典序前3的

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

int n;
int grap[10000][10000];
bool lie[10000], dui1[10000], dui2[10000];
vector[HTML_REMOVED]path;
//set[HTML_REMOVED] >set1;
vector[HTML_REMOVED] >set1;
void dfs(int floor)
{
if (floor == n)
{
//set1.insert(path);
set1.push_back(path);
return;
}
for (int i = 0; i < n; i)
{
if (!lie[i] && !dui1[floor + i] && !dui2[floor - i + n])
{
lie[i] = true;
dui1[floor + i] = true;
dui2[floor - i + n] = true;
path.push_back(i+1);//要注意号码的输出!现实生活中是没有0的,所以要加1,比如1 3 5 0 2 4,正确的应该是2 4 6 1 3 5!!!注意
dfs(floor+1);//层数要记着加1!!!
lie[i] = false;
dui1[floor + i] = false;
dui2[floor - i + n] = false;
path.pop_back();//pop_back(i),不接受参数,否会报错!!!,其他容器也要记住!!!
}
}
}
bool cmp(vector[HTML_REMOVED] num1, vector[HTML_REMOVED] num2)
{
for (int i = 0; i < num1.size(); i
)
{
if (num1[i] == num2[i])
continue;
else
return num1[i] < num2[i];
}
return true;
}
int main()
{
cin >> n;
int i = 0;
dfs(0);//要记着进行调用,别忘记,好几次都是这样
//cout << set1.size();
//方法1
/for (auto it = set1.begin(); it != set1.end(); it, i)//可以使用set容器进行排序,set中的元素是vector,可以直接用auto定义变量
{
if (i > 3)
break;
vector[HTML_REMOVED]num =
it;//这里要注意输出的形式,这样输出!
for (int i = 0; i < num.size(); i)
{
cout << num[i] << ‘ ‘;
}
cout << endl;
}*/
//方法2
//sort中cmp函数的用法
//如果0, 那么函数就会将他们互换位置, 1就会保持原来位置不变。
// 返回类型如果是Bool类型的话 就是true = 1,false = 0;
// 如果返回是0的话,那么它就会交换位置,如果是1,代表不需要动。
sort(set1.begin(), set1.end(), cmp);
for (int i = 0; i < 3; i
)
{
for (int j = 0; j < set1[i].size(); j++)
{
cout << set1[i][j] << ‘ ‘;
}
cout << endl;
}
cout << set1.size();
return 0;
}