洛谷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.在这道题当中,我们不采取一般的建图(姑且先用下这个词)方式——建一个二维数组。因为这样的话,我们需要更多的循环来支持占领操作。
我们分别为行、列、左斜线(/)、右斜线(\ ) 单独建立数组。
这样做的好处非常明显:在进行占据操作的时候,只需要在相对应的行、列、左斜、右斜打上标记就行,不需要在每一块都用循环进行操作,节省很多时间
更多推荐
洛谷P1219
发布评论