jzoj 1578. 【普及模拟】N皇后

发布于 2019-03-21  933 次阅读

题目描述

下图，就是一个大小为6的三角形棋盘：

图1给出的是皇后攻击范围的示例——每个皇后有三个方向可以自由攻击。

图2给出的是在一个三角形棋盘上的不能互相攻击的4个皇后。

现在，你有一个三角形棋盘，棋盘上已经放置了几个互相不能攻击的皇后，请问棋盘上最多还能放多少个皇后，使得她们仍然不能互相攻击；并求出有多少种方案可以放这么多皇后。

在输出中输出这两个数。

 

输入

第一行一个数字N，代表棋盘的大小。

接下来N行，第i行有i个字符。表示棋盘第i行的状态，‘.’表示空，‘*’表示有皇后。

输出

  两行，每行一个数字，分别为在原来的棋盘上最多能放的皇后数量，和放置这么多皇后的方案种数。

本质是一个少了一个条件在加多一些固定的皇后的八皇后问题，所以用搜索就可以了

 

var
  f,w:array[-10..100,-100..1000] of integer;
  i,j,k,n,m,l,max:longint;
  a,b,d,c,o:array[-100..10000] of longint;
  ch:string;
procedure dfs(x:longint);
var
  i,j,k:longint;
begin
  if x>n then
    begin
      exit;
    end;
  for i:=1 to x do
    begin
      if (f[x,i]=0) and (b[x-i]=0) and (d[i]=0) and (o[x]=0) then
        begin
          f[x,i]:=1;
          a[x+i]:=1;
          d[i]:=1;
          b[x-i]:=1;
          l:=l+1;
          if l>max then max:=l;
          inc(c[l]);
          dfs(x+1);
          f[x,i]:=0;
          d[i]:=0;
          a[x+i]:=0;
          b[x-i]:=0;
          l:=l-1;
        end
  //  else dfs(x+1);
    end;
end;

begin
assign(input,'queen.in');reset(input);
  assign(output,'queen.out');rewrite(output);
  readln(n);
  fillchar(f,sizeof(f),$7);
  for i:=1 to n do
    begin
      readln(ch);
      for k:=1 to i do
        if ch[k]='.' then f[i,k]:=0
          else begin
                 f[i,k]:=1;
                 d[k]:=1;
                 a[i+k]:=1;
                 b[i-k]:=1;
                 o[i]:=1;
                 inc(c[0]);
               end;
    end;

  for i:=1 to n do
  if o[i]<>1 then
   dfs(i);
   writeln(max);
   writeln(c[max]);
end.