欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Problem : 射击

程序员文章站 2022-04-05 12:37:06
...

Problem : 射击

Description
不难发现,豆豆能从很多事情中去思考数学,于是豆豆父母决定让他去练习射击,这是项需要集中注意力的运动,相信
能够让豆豆暂时脱离数学。学习射击的第一天就让豆豆产生 了浓厚的兴趣,射击的靶子是大饼圆,射击枪的子弹近
似圆柱,为什么要圆的不能是其他的 形状呢,于是豆豆开始构思,设计了这样一个好玩的问题:N*M 的方形格子靶子,
每个格子有两种状态凸或者凹(如下图浅色表示凹,深色表示凸)

现在用一个十字横截面的子弹(填充黑色部分)去射击,被射中的小格子凹变凸,凸变 凹,子弹放大后的横截面如下图

这种子弹最多可以覆盖 5 个格子,如图打完后,5 个格子凹凸状态发生了变化

请问最少需要几次射击使靶子中所有小格子都呈现凹的状态。
注意:子弹中心点如果打到四个角上则只会影响 3 个格子,如下图黑色格子表示被子 弹中心点正好击中左上角后覆
盖的 3 个格子,如果打到除四个角的边界上,则会影响到 4 个格子,如下图右侧的 4 个黑色格子所示,这是子弹中
心点打中第 3 行第 6 列时的覆盖情 况。(也就是说子弹超出靶子部分不起效)

Input
第一行两个用空格隔开的数字 N 和 M(1<=N,M<=17)
接下来 N 行 述靶子中小格子的状态,‘X’表示凸,‘.’表示凹。

Output
输出所需要的最少射击次数
注意:输入数据保证有解

Sample Input
【样例输入 1】
5 5
XX.XX
X.X.X
.XXX.
X.X.X
XX.XX

【样例输入 2】
8 9
..XXXXX..
.X…..X.
X..X.X..X
X…….X
X.X…X.X
X..XXX..X
.X…..X.
..XXXXX..
Sample Output
【样例输出 1】
5

【样例输出 2】
25

var
  map,b:array[0..18,0..18] of longint;
  st:array[0..18] of string;
  a:array[1..18] of longint;
  n,m,i,j,ans,sum:longint;
procedure chenge(x,y:longint);
begin
  b[x,y]:=b[x,y] xor 1;
  b[x-1,y]:=b[x-1,y] xor 1;
  b[x+1,y]:=b[x+1,y] xor 1;
  b[x,y-1]:=b[x,y-1] xor 1;
  b[x,y+1]:=b[x,y+1] xor 1;
  inc(sum);
end;
procedure s(x:longint);
var
  i,j:longint;
  f:boolean;
begin
  if x>m then
  begin
    sum:=0;
    for i:=1 to n do
    for j:=1 to m do b[i,j]:=map[i,j];
    for i:=1 to m do if a[i]=1 then chenge(1,i);
    for i:=2 to n do
    for j:=1 to m do if b[i-1,j]=1 then chenge(i,j);
    f:=true;
    for i:=1 to m do
    if b[n,i]=1 then f:=false;
    if f and (sum<ans) then ans:=sum;
    exit;
  end;
  a[x]:=0;
  s(x+1);
  a[x]:=1;
  s(x+1);
end;
begin
  readln(n,m);
  for i:=1 to n do readln(st[i]);
  for i:=1 to n do
  for j:=1 to m do
  if st[i,j]='X' then map[i,j]:=1
  else map[i,j]:=0;
  ans:=n*m;
  s(1);
  write(ans);
end.
相关标签: Pascal