首页 > 代码库 > 蓝桥杯 算法训练 ALGO-125 王、后传说
蓝桥杯 算法训练 ALGO-125 王、后传说
算法训练 王、后传说
时间限制:1.0s 内存限制:256.0MB
问题描述
地球人都知道,在国际象棋中,后如同太阳,光芒四射,威风八面,它能控制横、坚、斜线位置。
看过清宫戏的中国人都知道,后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围,但也总能找到相安无事的办法。
所有中国人都知道,皇权神圣,伴君如伴虎,触龙颜者死......
现在有一个n*n的皇宫,国王占据他所在位置及周围的共9个格子,这些格子皇后不能使用(如果国王在王宫的边上,占用的格子可能不到9个)。当然,皇后也不会攻击国王。
现在知道了国王的位置(x,y)(国王位于第x行第y列,x,y的起始行和列为1),请问,有多少种方案放置n个皇后,使她们不能互相攻击。
看过清宫戏的中国人都知道,后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围,但也总能找到相安无事的办法。
所有中国人都知道,皇权神圣,伴君如伴虎,触龙颜者死......
现在有一个n*n的皇宫,国王占据他所在位置及周围的共9个格子,这些格子皇后不能使用(如果国王在王宫的边上,占用的格子可能不到9个)。当然,皇后也不会攻击国王。
现在知道了国王的位置(x,y)(国王位于第x行第y列,x,y的起始行和列为1),请问,有多少种方案放置n个皇后,使她们不能互相攻击。
输入格式
一行,三个整数,皇宫的规模及表示国王的位置
输出格式
一个整数,表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
n<=12
示例代码:
1 import java.io.BufferedReader; 2 import java.io.IOException; 3 import java.io.InputStreamReader; 4 5 public class Main { 6 public static int n = 0; //皇宫的大小 7 public static int x = 0; //皇上横坐标位置(注:从1开始) 8 public static int y = 0; //皇上纵坐标的位置(注:从1开始) 9 public static int[] column_num; //所放皇后的列号 10 public static int[][] palace; //皇宫 11 public static int count = 0; //几种方案 12 13 public static void main(String[] args) throws IOException { 14 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 15 String[] str = br.readLine().split(" "); 16 n = Integer.parseInt(str[0]); 17 x = Integer.parseInt(str[1]); 18 y = Integer.parseInt(str[2]); 19 20 int k = x-2 > 0 ? x-2 : 0; //皇上行范围的开始位置 21 int m = y-2 > 0 ? y-2 : 0; //皇上列范围的开始位置 22 x = x > n-1 ? n-1 : x; //皇上行范围的结束位置 23 y = y > n-1 ? n-1 : y; //皇上列范围的结束位置 24 25 column_num = new int[n]; 26 palace = new int[n][n]; 27 28 for(int i = k; i <= x; i++){ //皇上范围置-1 29 for(int j = m; j <= y; j++){ 30 palace[i][j] = -1; 31 } 32 } 33 34 place(0); 35 36 System.out.println(count); //输出方案数 37 38 } 39 40 //放皇后 41 private static void place(int num) { 42 if(num == n){ //如果已经放完了 43 count++; 44 }else{ 45 for(int column = 0; column < n; column++){ //列变化 46 if(palace[num][column] == -1){ 47 continue; 48 } 49 column_num[num] = column; //记录列号 50 boolean flag = true; 51 for(int number = 0 ; number < num; number++){ //用放置好的去验证它是否放置准确 52 if(column_num[num] == column_num[number] || //是否在列 53 num + column_num[num] == number + column_num[number] || //是否在左对角线 54 num - column_num[num] == number - column_num[number]){ //是否在右对角线 55 flag = false; 56 break; 57 } 58 } 59 60 if(flag){ //如果放置好了,就去放置下一个皇后 61 place(num+1); 62 } 63 } 64 } 65 } 66 67 }
蓝桥杯 算法训练 ALGO-125 王、后传说
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。