题目描述

有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.