BASIC-27_蓝桥杯_2n皇后问题

题目:

问题描述
  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。
输入格式
  输入的第一行为一个整数n,表示棋盘的大小。
  接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。
输出格式
  输出一个整数,表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
 
思路:
1:先列出黑皇后的情况,再进入至白皇后的搜索(黑、白皇后分开写,便于回溯);
2:之前一直会出错是由于黑白皇后都在一个函数中递归,条件没设置好(烦),导致在回溯失败;
 
示例代码:

#include <stdio.h>
#define N 8

int n = 0 ;
int f[N][N] = {0};
int sum = 0;
int flag = 0;

/*同一行、同一列、对角线 为 0*/
void change(int i , int j , int k , int num[][N])
{
  int tmp = 0 ;
  int x = 0 , y = 0 ;
  /*由于是从上至下搜索,可以考虑删去对上面的处理*/
  //N = 5;
  //int arr[N][2] = {{0,-1},{0,1},{1,-1},{1,0},{1,1},};
  int arr[N][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1},};
  for (tmp = 0 ; tmp < N ; tmp ++)
  {
    x = i + arr[tmp][0] ;
    y = j + arr[tmp][1] ;
    while(x >= 0 && y >= 0 && x < n && y < n)
    {
      num[x][y] = k;
      x += arr[tmp][0];
      y += arr[tmp][1];
    }
  }
  return ;
}

void dfs_2n(int step , int map[][N])
{
  int x = 0 , y = 0 ;
  int i = 0 , j = 0 , k = 0 ;
  int tmp[N][N] = {0};
  if (step == n )
  {
    sum ++;
    #if 0/*打印棋盘.黑皇后->2,白皇后->3*/
    printf("====================\n");
    for (x = 0 ; x < n ; x ++)
    {
      for (y = 0 ; y < n ; y ++)
        printf("%d ",f[x][y]);
      printf("\n");
    }
    #endif
    return ;
  }
  for (j = 0 ; j < n ; j ++)
  {
    if (map[step][j])
    {
      map[step][j] = 0;
      f[step][j] = 3; /*白皇后->3*/
      for (x = 0 ; x < n ; x ++)
      {
        for (y = 0 ; y < n ; y ++)
        {
          tmp[x][y] = map[x][y];
        }
      }
      change(step,j,0,tmp);
      dfs_2n( step+1 , tmp);
      map[step][j] = 1;
      f[step][j] = 1;
    }
  }
  return ;
}

void dfs_1n(int step , int map[][N])
{
  int x = 0 , y = 0 ;
  int i = 0 , j = 0 ;
  int tmp[N][N] = {0};

  if (step == n )
  {
    for (i = 0 ; i < n ; i ++)
    {
      for (j = 0 ; j < n ; j ++)
      {
        if (f[i][j] == 1)
          map[i][j] = 1;
        else
          map[i][j] = 0;
      }
    }
    dfs_2n( step%n , map);
    return ;
  }

  for (j = 0 ; j < n ; j ++)
  {
    if (map[step][j])
    {
      map[step][j] = 0;
      f[step][j] = 2;/*黑皇后->2*/
      for (x = 0 ; x < n ; x ++)
      {
        for (y = 0 ; y < n ; y ++)
        {
          tmp[x][y] = map[x][y];
        }
      }
      change(step,j,0,tmp);
      dfs_1n( step+1 , tmp);
      map[step][j] = 1;
      f[step][j] = 1;
    }
  }
  return ;
}

int main(void)
{
  int i = 0 , j = 0 ;
  int map[N][N] = {0};
  scanf("%d",&n);
  for (i = 0 ; i < n ; i ++)
  {
    for (j = 0 ; j < n ; j ++)
    {
      scanf("%d",&map[i][j]);
      f[i][j] = map[i][j];
    }
  }

  dfs_1n(0,map);

  printf("%d",sum);
  return 0;
}

上一篇:The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar


下一篇:APP打开(二)—标准流程