i use clear binmask as in 1122, but in 1122 u can chek for answer your board by every change of bit, BUT in THIS problem, u need check board when you finish your changes with bits.
Example u have bits 1101 and next is 1110,
u firstly change 1111 and then 1110 (two iterations because we need to do this iterations on board)
so if u do check on every that iteration its wa19

this is can be possible

what is the answer for the following test
bbbb
wwwb
wbwb
wbbb

my AC code shows that answer is 7, is that right?

needn't all 2^16 search, divide it two part each 8 bit.

wwww
wwww
wwww
wwww

Gimme The 10 Test pls!!!

Can anyone please provide test case #11? I am getting WA on that.

I wonder the teat #9...

How answer is 4 . If we flip 16 pieces , then answer is 4 ? Is it true ? Thanks .

I don't know why...
I just use full search...
O(2^16)
but how can so fast?
http://acm.timus.ru/status.aspx?space=1&num=1060&author=40909

Edited by author 26.12.2006 14:56

if WA9, try to check

wwww
wwww
wwwb
wwbb

ans=1

My solution:

program p1060;
type
  frr=array[0..5,0..5] of boolean;
var
  f:frr;
  ans:byte;
procedure init;
  var
    i,j:byte;
    ch:char;
  begin
    fillchar(f,sizeof(f),true);
    for i:=1 to 4 do
      begin
        for j:=1 to 4 do
          begin
            read(ch);
            if ch='b'
              then f[i,j]:=false;
          end;
        readln;
      end;
  end;
function check(f:frr):boolean;
  var
    b:boolean;
    i,j:byte;
  begin
    b:=f[1,1];
    for i:=1 to 4 do
      for j:=1 to 4 do
        if f[i,j]<>b
          then exit(false);
    exit(true);
  end;
function min(a,b:byte):byte;
  begin
    if a<b
      then exit(a)
      else exit(b);
  end;
procedure find(f:frr;x,y,t:byte);
  begin
    if check(f)
      then begin
             ans:=min(ans,t);
             exit;
           end;
    if x>4
      then exit;
    if y=4
      then find(f,x+1,1,t)
      else find(f,x,y+1,t);
    f[x,y]:=not(f[x,y]);
    f[x-1,y]:=not(f[x-1,y]);
    f[x+1,y]:=not(f[x+1,y]);
    f[x,y-1]:=not(f[x,y-1]);
    f[x,y+1]:=not(f[x,y+1]);
    if y=4
      then find(f,x+1,1,t+1)
      else find(f,x,y+1,t+1);
  end;
procedure outit;
  begin
    if ans=17
      then writeln('Impossible')
      else writeln(ans);
  end;
begin
  init;
  ans:=17;
  find(f,1,1,0);
  outit;
end.

Edited by author 07.05.2009 11:48

Edited by author 07.05.2009 11:49

please, help me to find a bug, or give me some tests

Here is my code.

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <stdio.h>

#define MAX_VAL 100

using namespace std;

int res = -1;

vector<int> mem;

void go(bool a[4][4],int cur) {
    long hex = 0,step = 1;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (a[i][j]==1) hex+=step;
            step*=2;
        }
    }

    if (hex==65535) {
        if (cur<res||res==-1) res = cur;
        return;
    }

    if (cur<mem[hex]) {
        mem[hex] = cur;

        int mov[4][2];

        mov[0][0] = 1; mov[0][1] = 0;
        mov[1][0] = -1;mov[1][1] = 0;
        mov[2][0] = 0; mov[2][1] = 1;
        mov[3][0] = 0; mov[3][1] = -1;


        for (int x = 0; x < 4; x++) {
            for (int y = 0; y < 4; y++) {
                bool next[4][4];

                for (int w1 = 0; w1 < 4; w1++) for (int w2 = 0; w2 < 4; w2++) next[w1][w2] = a[w1][w2];

                for (int k = 0; k < 4; k++) {
                    int nx = x+mov[k][0],ny = y+mov[k][1];

                    if (nx>=0&&ny>=0&&nx<4&&ny<4)
                        next[nx][ny] = 1-next[nx][ny];// flip
                }
                next[x][y] = 1-next[x][y];

                go(next,cur+1);
            }
        }
    }
}

int main() {
    bool a[4][4],f = true;

    string s;
    for (int i = 0; i < 4; i++) {
        cin >> s;
        for (int j = 0; j < 4; j++) {
            if (s[j]=='w') a[i][j] = 0;
            else {
                a[i][j] = 1;
                f = false;
            }
        }
    }
    if (f) {
        cout << "0";
        return 0;
    }

    for (long x = 0; x < 1<<16+1; x++) mem.push_back(MAX_VAL);

    go(a,0);

    if (res==-1) cout << "Impossible";
    else cout << res;

    return 0;
}

When should the program write('inpossible');

I get wrong answer at test 3?
why?
this is my program:
program gh;
const
 x:array[1..4] of integer=(-1,0,1,0);
 y:array[1..4] of integer=(0,-1,0,1);
var
 a,d,f,g,h,j,k,i,l,m,n:longint;
 s,z,c:string;
 procedure work(q:integer);
 var
  i,j,k,l:longint;
  v:string;
 begin
  if q=17 then
   begin
    if (pos('w',s)=0) and (g<m) then
     m:=g;
   end
  else
   begin
    v:=s;
    i:=((q-1) div 4)+1;
    j:=q-(i-1)*4;
    if s[q]='w' then
     s[q]:='b'
    else
     s[q]:='w';
    for l:=1 to 4 do
     if (i+y[l]>0) and (i+y[l]<5) and  (j+x[l]<5) and (j+x[l]>0) then
      if s[(i+y[l]-1)*4+j+x[l]]='w' then
       s[(i+y[l]-1)*4+j+x[l]]:='b'
      else
       s[(i+y[l]-1)*4+j+x[l]]:='w';
    g:=g+1;
    work(q+1);
    g:=g-1;
    s:=v;
    work(q+1);
   end;
 end;
begin
 s:='';
 for i:=1 to 4 do
  begin
   readln(z);
   s:=s+z;
  end;
 g:=0;
 m:=1000000;
 work(1);
 if m=1000000 then
  writeln('Impossible')
 else
  writeln(m);
end.

Edited by author 06.09.2006 18:24

Actually, i can't catch the idea of the problem... It seems to me
that simple searching isn't good... but what then??