算法训练王、后传说

时间限制：1.0s 内存限制：256.0MB

问题描述

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

输入格式

　　一行，三个整数，皇宫的规模及表示国王的位置

输出格式

　　一个整数，表示放置n个皇后的方案数

样例输入

8 2 2

样例输出

数据规模和约定

　　n<=12

import java.util.Scanner;
public class Main {
    static int n,x,y,ans;
    static int palace[][]=new int[20][20];
    static void init(){
        
        int i,j;
        for(i=0;i<20;i++){
            for(j=0;j<20;j++){
                palace[i][j]=0;
            }
        }
        for(i=x-1;i<=x+1;i++){
            for(j=y-1;j<=y+1;j++){
                palace[i][j]=1000000;
            }
        }
        ans=0;
    }
    
    static int judge(int row,int col){
        int i,j;
        for(i=row-1,j=col-1;i>=1 && j>=1;i--,j--){
            if(palace[i][j]==1){
                return 0;
            }
        }
        for(i=row-1,j=col+1;i>=1 && j<=n;i--,j++){
            if(palace[i][j]==1){
                return 0;
            }
        }
        for(i=row-1,j=col;i>=1;i--){
            if(palace[i][j]==1){
                return 0;
            }
        }
        return 1;
    }
    static void countScheme(int r){
        if(r>n){
            ans++;
            return;
        }
        int i;
        
        for(i=1;i<=n;i++){
            if(palace[r][i]==1000000){
                continue;
            }
            
            if(judge(r,i)==1){
                palace[r][i]=1;
                countScheme(r+1);
                palace[r][i]=0;
            }
            else{
                continue;
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        x=sc.nextInt();
        y=sc.nextInt();
        init();
        countScheme(1);
        System.out.println(ans);
        

    }

}

算法训练 王、后传说

算法训练王、后传说