Link

题意

分析

N皇后问题，但是是给出地图，地图上为\('.'\)的点不能放。

如果直接用普通的DFS会有3个点超时。需要用到位运算。

• 逐行放置皇后，首先排除每行有多个皇后互相排斥的情况；

• 用\(st[r]\)来存储\(r\)这一行的状态，将'.'的位 置为1；

• dfs保存四个参数:当前为第几行、当前行的(列)状态、从右上到左下对角线的状态(\(<<1\))、从左上到右下对角线的状态(\(>>1\))；

• 获取当前哪一位可以放置皇后:将四者取并集(即将四者进行或运算).得到的状态中为0的就可以放置皇后；

• 为了快速得到可以放置皇后的位置，对上一步得到的状态进行取反.转换成快速得到1的位置 (用\(lowbit\)可以得到从右往左的第一个1)；

• 将状态中的1减掉，继续找下一个1；

• 更新"将是下一行的状态"，由于对角线是斜着影响的，所以右上到左下对角线的状态需要左移一位、左上到右下对角线的状态需要右移一位；

• 知道当前行的状态全为1时，即每一行都有一个皇后时，res++；

package main

import (
    "bufio"
    . "fmt"
    "os"
)

var n, res, all int
var st []int

func lowBit(x int) int {
    return x & -x
}

func dfs(r, colState, d1State, d2State int) {
    if colState == all { // 全部都是1了
        res++
        return
    }
    // 取并集之后，本来是0的位置可以放，但是取返之后就是1的位置可以放，再和整个状态取一个&，得到当前行可以放的列(某一位=1)的列
    rOneAllCan := all & (^(colState | d1State | d2State | st[r])) // go去反是^, c是~
    for rOneAllCan != 0 {
        p := lowBit(rOneAllCan) // 从右往左找到第一个1
        rOneAllCan -= p         // 去掉最后一个1，等下还要找第二个1
        dfs(r+1, colState+p, (d1State+p)<<1, (d2State+p)>>1)
    }
}

func main() {
    r, w := bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
    defer w.Flush()

    Fscan(r, &n)
    all = 1<<n - 1
    st = make([]int, n)

    var s string
    for i := 0; i < n; i++ {
        Fscan(r, &s)
        for j := 0; j < n; j++ {
            if s[j] == '.' {
                st[i] |= 1 << j
            }
        }
    }
    dfs(0, 0, 0, 0)

    Fprintf(w, "%d\n", res)
}

超时版本:

package main

import (
    "bufio"
    . "fmt"
    "os"
)

var n, res int
var col, d1, d2 []bool
var chess [][]byte

func dfs(r int) {
    if r >= n {
        res++
        return
    }
    for c := 0; c < n; c++ {
        id1, id2 := r+c, c-r+n-1 // 主对角线/对角线
        if col[c] || d1[id1] || d2[id2] || chess[r][c] == '.' {
            continue
        }
        col[c], d1[id1], d2[id2] = true, true, true
        dfs(r + 1)
        col[c], d1[id1], d2[id2] = false, false, false
    }
}

func main() {
    r, w := bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
    defer w.Flush()

    Fscan(r, &n)
    col, d1, d2 = make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
    chess = make([][]byte, n)

    var s string
    for i := range chess {
        Fscan(r, &s)
        chess[i] = []byte(s)
    }
    dfs(0)

    Fprintf(w, "%d\n", res)
}