Next Nest

wusa!~(•㉨•)

「題解】USACO1.5 - Checker Challenge

发表于 Valine：

QUST 2020級第三學期算法數據結構測試 Contest1121 T4
原題來自 USACO1.5 Checker Challenge, 洛谷 P1219

Problem Description

一個如下的 6 x 6 的跳棋棋盤，有六個棋子被放置在棋盤上，使得每行、每列有且只有一個，每條對角線（包括兩條主對角線的所有平行線）上至多有一個棋子。

0   1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

上面的佈局可以用序列 2 4 6 1 3 5 來描述，第 k 個數字表示在第 k 行的相應位置有一個棋子，如下：

行號 1 2 3 4 5 6

列號 2 4 6 1 3 5

這只是棋子放置的一個解。請編一個程序找出所有棋子放置的解。
並把它們以上面的序列方法輸出，解按字典順序排列。
請輸出前 3 個解。最後一行是解的總個數。

Inputs

一行一個正整數 m，表示棋盤是 m x m 大小的。

Outputs

前三行為前三個解，每個解的兩個數字之間用一個空格隔開。
第四行只有一個數字，表示解的總數。

Samples

  • Sample #1

    • Inputs

      1
      6

    • Outputs

      1
      2
      3
      4
      2 4 6 1 3 5
      3 6 2 5 1 4
      4 1 5 2 6 3
      4

Details

  • 數據范圍：對於 100% 的數據，6 <= n <= 13。
  • 題目翻譯來自NOCOW。
  • USACO Training Section 1.5

Analysis

Solution Program

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
using namespace __gnu_cxx;

int main(int argc, char *argv[]) {
    return 0;
}

Alternative Solution by ybb756032937

搜索、標記、回溯ybb756032937
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
//不建議採用頭文件`bits/stdc++.h`，可能和定義的變量或名字起衝突，從而引起編譯錯誤；
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int a[100],b[100],c[100],d[100];
//a數組表示的是行；
//b數組表示的是列；
//c表示的是左下到右上的對角線；
//d表示的是左上到右下的對角線；
int total;//總數:記錄解的總數
int n;//輸入的數，即N*N的格子，全局變量，搜索中要用
int print()
{
    if(total<=2)//保證只輸出前三個解，如果解超出三個就不再輸出，但後面的total還需要繼續疊加
    {
        for(int k=1;k<=n;k++)
        cout<<a[k]<<" ";//for語句輸出
        cout<<endl;
    }
    total++;//total既是總數，也是前三個排列的判斷
}
void queen(int i)//搜索與回溯主體
{
    if(i>n)
    {
        print();//輸出函數，自己寫的
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)//嘗試可能的位置
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果沒有皇后佔領，執行以下程序
            {
                a[i]=j;//標記i排是第j個
                b[j]=1;//宣布佔領縱列
                c[i+j]=1;
                d[i-j+n]=1;
                //宣布佔領兩條對角線
                queen(i+1);//進一步搜索，下一個皇后
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
                //（回到上一步）清除標記
            }
        }
    }
}
int main()
{    
    cin>>n;//輸入N*N網格，n已在全局中定義
    queen(1);//第一個皇后
    cout<<total;//輸出可能的總數
    return 0;
}
  • 注：對角線d[i-j]後面必須加上一個n，因為i-j可能為負數，那麼數組就會出錯，所以將整體向右偏移n個單位（坐標偏移不會影響我們需要達到的目的），將所有可能變成正數；（因為i-j的最小值是-n+1，所以加上一個n就一定會變成一個正數）
  • 本道題最重要的就是記錄下皇后佔領的格子（打標記的思想），通過此判斷下一個皇后是否可以在某個位置，如果可以，則繼續搜索下一個皇后可以在的位置，如果不行，則清除標記回到上一步，繼續搜索；
  • 可以先考慮六個皇后（即6*6網格)，再將6改為n，並且輸入n，就可以得出6到13個皇后的解了；