首页 > 代码库 > 算法训练 王、后传说

算法训练 王、后传说

2024-09-08 12:11:30   220人阅读

问题描述
　　地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、坚、斜线位置。
　　看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
　　所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死......
　　现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王在王宫的边上，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
　　现在知道了国王的位置（x,y）（国王位于第x行第y列，x,y的起始行和列为1），请问，有多少种方案放置n个皇后，使她们不能互相攻击。
输入格式
　　一行，三个整数，皇宫的规模及表示国王的位置
输出格式
　　一个整数，表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
　　n<=12
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
    static int n;
    static int[] zhu ;
    static int[] fu;
    static int[] lie;
    static int[][] a;
    static int sum = 0;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        int x = input.nextInt();
        int y = input.nextInt();
        fu = new int[2*n];
        zhu = new int[2*n];
        lie = new int[n+1];
        a = new int[n+2][n+2];
        a[x][y] = 1;
        a[x][y-1] = 1;
        a[x][y+1] = 1;
        a[x+1][y] = 1;
        a[x+1][y-1] = 1;
        a[x+1][y+1] = 1;
        a[x-1][y] = 1;
        a[x-1][y-1] = 1;
        a[x-1][y+1] = 1;
        //i+j-1;
        //j-i+n;
        f(1);
        System.out.println(sum);
    }
    public static  void f(int i){
        for(int j=1;j<=n;j++){
            if(a[i][j]==1||lie[j]==1||fu[i+j-1]==1||zhu[j-i+n]==1)
            continue;
            lie[j] = 1; fu[i+j-1] = 1;zhu[j-i+n] = 1;
            if(i==n){
                sum++;
            }else{
                f(i+1);
            }
            lie[j] = 0;fu[i+j-1] = 0;zhu[j-i+n] = 0;
        }
        
    }
    
    
}

 

算法训练 王、后传说


联系
我们