1128. N Queens Puzzle 解析

1128. N Queens Puzzle 解析

这个棋盘的下标也是有点厉害，从左下角开始的。想了半天。

行和斜向的都不能在一条直线，分别计算出下标，然后看又没有在一条直线上的。

a[i-1][j-1]  a[i-1][j]  a[i-1][j+1]

a[i][j-1]      a[i][j]      a[i][j+1]

a[i+1][j-1]  a[i+1][j]  a[i+1][j+1]

看清楚行列。应该没什么问题了。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>using namespace std;
vector <int> queens;
int k, n;bool map[1005][1005];
bool horizon[1005];bool CheckMap(int h ,int v) {//h = row ; v = columnif (horizon[h]) {return false;}else {horizon[h] = true;}if (map[h][v])return false;else {for (int row = h,column = v; row >= 0 && column >= 0 && row <= n && column <= n;row++,column++) {//row行 column列if (map[row][column])return false;}for (int row = h, column = v; row >= 0 && column >= 0 && row <= n && column <= n; row++, column--) {//row行 column列if (map[row][column])return false;}for (int row = h, column = v; row >= 0 && column >= 0 && row <= n && column <= n; row--, column++) {//row行 column列if (map[row][column])return false;}for (int row = h, column = v; row >= 0 && column >= 0 && row <= n && column <= n; row--, column--) {//row行 column列if (map[row][column])return false;}map[h][v] = true;}return true;}int main() {cin >> k;for (int i = 1; i <= k; i++) {cin >> n;int qn;bool tag = true;memset(map, false, sizeof(map));memset(horizon, false, sizeof(horizon));for (int j = 1; j <= n; j++) {cin >> qn;if (tag)tag = CheckMap(qn, j);//先行 后列			}if (tag)cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}