洛谷P1219

洛谷P1219"/>

洛谷P1219

洛谷P1219

文章目录

• 洛谷P1219
• 一、题目描述
• 二、代码
• 记录

一、题目描述

二、代码

代码如下：

#include <bits/stdc++.h>
using namespace std;int n;
int hang[105], lie[105], lxie[105], rxie[105];void print(){for(int i = 1; i <= n; i++){cout << hang[i] << " ";}cout << endl;
}void dfs(int index, int &count){if(index > n){if(count < 3){print();}count++;return;}for(int i = 1; i <= n; i++){if(!lie[i] && !lxie[i-index+n] && !rxie[index+i]){hang[index] = i;lie[i] = 1;lxie[i-index+n] = 1;rxie[i+index] = 1;dfs(index+1, count);lie[i] = 0;lxie[i-index+n] = 0;rxie[i+index] = 0;}}
}int main (){int count = 0;cin >> n;memset(lie, 0, sizeof(lie));memset(hang, 0, sizeof(hang));memset(lxie, 0, sizeof(lxie));memset(rxie, 0, sizeof(rxie));dfs(1, count);cout << count << endl;	
}

记录

1.第一次练习使用DFS深搜。

2.在这道题当中，我们不采取一般的建图（姑且先用下这个词）方式——建一个二维数组。因为这样的话，我们需要更多的循环来支持占领操作。
我们分别为行、列、左斜线（/)、右斜线(\ ) 单独建立数组。
这样做的好处非常明显：在进行占据操作的时候，只需要在相对应的行、列、左斜、右斜打上标记就行，不需要在每一块都用循环进行操作，节省很多时间