棋盘挑战
本文最后更新于 500 天前,其中的信息可能已经有所发展或是发生改变。

Original Link

思想

  • DFS
  • 注意棋盘的每一行,每一列及其有棋子存在的对角线的平行线上有且只有一个棋子。
  • 递归处理,每一次递视为一次对是否放置棋子的判断,递归的层数视为棋盘的层数,每一层只能放置一个棋子。
  • 对于递归的每一层,遍历这层棋盘的格子,判断以该格子的列和对角线的平行线上是否存在过棋子:
    • 没有棋子则直接放置,标记并递归进入下一层,以此种方法可以得到最小字典序的方案。
    • 放置棋子后,则需要对放置的格子所在的列和对角线的平行线进行标记。
  • 递归处理上述过程,直到将所有的棋子放置完毕,记录 res 为方案数,res <= 3 输出当前方案。
  • 对于对角线的处理,利用数学关系,将对角线的判断转换为对截距的判断,即放置的棋子的截距各不相同。截距可以数学关系推出 k = i + uk = i - u,另,由于 i - u 的值可能为负数,因此考虑增加偏移量 k = i - u + n 保证下标合法。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

bool y[N], l[N], r[N];

int n, res;

int ans[N];

void dfs(int u){
    if(u == n){  // 说明放满了棋子
        res ++;  // 记录答案 res + 1
        if(res <= 3){  // res <= 3 输出方案
           for(int i = 0; i < n; i ++) cout << ans[i] << ' ';
           cout << endl;
        }
        return ;
    }

    for(int i = 0; i < n; i ++){
        if(!y[i] && !l[u + n + i] && !r[u + n - i]){
            y[i] = l[u + n + i] = r[u + n - i] = 1;  // 标记
            ans[u] = i + 1;  // 存入答案数组
            dfs(u + 1);  // 递归到下一层
            y[i] = l[u + n + i] = r[u + n - i] = 0;  // 恢复现场
        }
    }
}

void solve(){
    cin >> n;
    dfs(0);
    cout << res << endl;
}

int main(){
    solve();
    return 0;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇