Poj Solution 1681

http://poj.org/problem?id=1681

//* @author:
import java.util.*;

public class Main {

 static Scanner in = new Scanner(System.in);
 static char[][] board;//���ڱ����ʼ״̬
 static boolean[][] map;//ǽ�ڵ�״̬
 static int cnt;//Ϳ��Ĵ���
    
 static void click(int x, int y) {//Ϳ��x,y)���ĸ���
    ++cnt;
    map[x][y] = !map[x][y];
    if(x-1>=0) map[x-1][y] = !map[x-1][y];//����ĸ���
    if(y-1>=0) map[x][y-1] = !map[x][y-1];//��ߵĸ���
    if(x+1< map.length) map[x+1][y] = !map[x+1][y];//����ĸ���
    if(y+1< map[x].length) map[x][y+1] = !map[x][y+1];//�ұߵĸ���
  }
    

 static int check(int s) {
   cnt = 0;
  for(int i=0; i!=map.length; ++i)//��ʼ״̬
    for(int j=0; j!=map[i].length; ++j)
        map[i][j] = board[i][j]=='w';
  for(int i=0; i!=map[0].length; ++i)//ȷ����һ�еľ������
           if((s&(1<< i))!=0)
        click(0, i);
                
  for(int i=1; i!=map.length; ++i)//Ϳ�ڶ��������һ��
       for(int j=0;j!=map[i].length; ++j)
        if(map[i-1][j]) click(i, j);
                
  for(int j=0; j!=map[map.length-1].length; ++j)//������һ���Ƿ�ȫ�ǻ�ɫ
    if(map[map.length-1][j]) return Integer.MAX_VALUE;
        return cnt;
  }
    
    
 public static void main(String[] args) {
   int t = in.nextInt();//���Դ���
   while(t-->0) {
    int n = in.nextInt();//���ӵĹ�ģ
    board = new char[n][];
    for(int i=0; i!=n; ++i) {
        board[i] = in.next().toCharArray();
    }
    map = new boolean[n][n];
    int ans = Integer.MAX_VALUE;
    for(int i=0; i!=(1 << n); ++i) {//��һ����2^n�ֱ仯����ÿһ�ֱ仯����
        ans = Math.min(ans, check(i));
    }
    if(ans< Integer.MAX_VALUE) System.out.println(ans);
    else System.out.println("inf");
   }
 }

}