tyvj 一个神奇的搜索

发布于 2019-04-04  36 次阅读


题目描述

有4*4的正方形,每个格子要么是黑色,要么是白色,当把一个格子的颜色改变(黑->白或者白->黑)时,其周围上下左右(如果存在的话)的格子的颜色也被翻转,问至少翻转几个格子可以使4*4的正方形变为纯白或者纯黑?

输入

输入共4行,每行4个字母,每个字母要么为w要么为b,分别表示初始时该格子上的颜色是白色还是黑色。

输出

输出仅1行,包含1个整数,表示变为纯白或者纯黑的最少翻转次数,若无解,输出”Impossible”。

思路

每次枚举要换多少个,然后进行搜索,经过严密的推算,本题最高只用进行5次交换就可以了。。。

var
  a,b:array[0..5,0..5] of integer;
  f:array[0..5,0..5] of boolean;
  i,j,k,n,m,s,x,y :longint;
  st:string;

procedure find;
var
  i,j,k,x,y:longint;
begin
  x:=a[1,1];
  for i:=1 to 4 do
    for j:=1 to 4 do
      if x<>a[i,j] then exit;
  writeln(n);
  halt;
end;

procedure dfs(dep:longint);
var
  i,j,k:longint;
begin
  if dep>n then begin find; exit; end;
  for i:=1 to 4 do
    for j:=1 to 4 do
      if not f[i,j] then
        begin
          f[i,j]:=true;
          a[i,j]:=abs(a[i,j]-1);
          a[i-1,j]:=abs(a[i-1,j]-1);
          a[i,j-1]:=abs(a[i,j-1]-1);
          a[i+1,j]:=abs(a[i+1,j]-1);
          a[i,j+1]:=abs(a[i,j+1]-1);
          dfs(dep+1);
          f[i,j]:=false;
          a[i,j]:=abs(a[i,j]-1);
          a[i-1,j]:=abs(a[i-1,j]-1);
          a[i,j-1]:=abs(a[i,j-1]-1);
          a[i+1,j]:=abs(a[i+1,j]-1);
          a[i,j+1]:=abs(a[i,j+1]-1);
        end;
end;

begin
  for i:=1 to 4 do
    begin
      readln(st);
      for j:=1 to 4 do
        if st[j]='b' then a[i,j]:=1;
    end;
  find;
  b:=a;
  for n:=1 to 5 do
    begin
      dfs(1);
      a:=b;
    end;
  writeln('Impossible');
end.
]]>