做题记录2022.2.7(ac:100%)

解题思路:采用深度优先搜索和回溯

                是8皇后问题的拓展和延伸

注意事项:

参考代码:

def check(row, column, pattern):
    global white, black, list1
    each = 0
    # print(row)
    if pattern == "white":
        while each <= row:#此处不要用for x in range(),无法处理第0行的情况,改用while循环
            if white[each] == column or white[each] + each == row + column or white[each] - each == column - row:#检测是否在同一列,对角线(对角线上的点分别满足一次函数y=x+c及y=-x+c)
                return False
            elif list1[row * n + column] != 1:#检测是否已经放置过其它
                return False
            each += 1
        return True # return True要在所有判断结束之后,原本代码写错导致我在这里卡了1个半小时,心态炸裂
    else:
        while each <= row:
            if black[each] == column or black[each] + each == row + column or black[each] - each == column - row:
                return False
            elif list1[row * n + column] != 1:
                return False
            each += 1
        return True


def dfs(row, pattern):#参数使用当前行数和所处模式(白和黑两种)
    global white, black, count, n, list1
    # print(row)
    if row == n:#当row到达n时,有两种情况,一种是白皇后已经放完要继续放黑皇后,另一种是黑皇后放完,计数+1,并进行回溯
        if pattern == "white":
            dfs(0, "black")
        elif pattern == "black":
            # print(white, black)
            count += 1
        return None
    else:
        if pattern == "white":
            for c in range(n):#遍历该行的所有列
                if check(row, c, pattern):#如果可以放置
                    white[row] = c#将white数组中对应行数白皇后的列数存入                    
                    list1[row * n + c] = 2#更改二维数组对应索引的数据值为2(2表示白皇后,3表示黑皇后)
                    # print(white, black, list1)
                    dfs(row + 1, pattern)#递归调用自身进行下一行的判定
                    white[row] = 100#当调用结束时,将对应值复原(回溯算法),设定为100是为了避免在check代码中与条件冲突,导致特定情况不被纳入
                    list1[row * n + c] = 1
        else:
            for c in range(n):
                if check(row, c, pattern):
                    black[row] = c
                    list1[row * n + c] = 3
                    # print(white, black, list1)
                    dfs(row + 1, pattern)
                    black[row] = 100
                    list1[row * n + c] = 1


n = int(input())
white, black, list1 = [x + 100 for x in range(n)], [x + 100 for x in range(n)], [] #此处的数组分别用于标记第i行的白,黑皇后,white[i],black[i]表示所处i行第几列
count = 0
for i in range(n):
    list1.extend(list(map(int, input().strip().split())))

dfs(0, "white")
print(count)