POJ.1222 EXTENDED LIGHTS OUT

1.Problem
http://poj.org/problem?id=1222

2.Idea
Flipping

3.Source

 #define MAX_M 15  
 #define MAX_N 15  
 const int dx[5] = { -1, 0, 0, 0, 1 };  
 const int dy[5] = { 0, -1, 0, 1, 0 };  
 int N, M;  
 int tile[MAX_M][MAX_N];  
 int opt[MAX_M][MAX_N];  
 int flip[MAX_M][MAX_N];  
 int get(int x, int y)  
 {  
      int c = tile[x][y];  
      for (int d = 0; d < 5; d++) {  
           int x2 = x + dx[d], y2 = y + dy[d];  
           if (0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {  
                c += flip[x2][y2];  
           }  
      }  
      return c % 2;  
 }  
 int calc()  
 {  
      for (int i = 1; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                if (get(i - 1, j) != 0) {  
                     flip[i][j] = 1;  
                }  
           }  
      }  
      for (int j = 0; j < N; j++) {  
           if (get(M - 1, j) != 0) return -1;  
      }  
      int res = 0;  
      for (int i = 0; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                res += flip[i][j];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int res = -1;  
      for (int i = 0; i < 1 << N; i++) {  
           memset(flip, 0, sizeof flip);  
           for (int j = 0; j < N; j++) {  
                flip[0][N - j - 1] = i >> j & 1;  
           }  
           int num = calc();  
           if (num >= 0 && (res < 0 || res > num)) {  
                res = num;  
                memcpy(opt, flip, sizeof(flip));  
           }  
      }  
      if (res < 0) {  
           cout << "IMPOSSIBLE" << endl;  
      }  
      else {  
           for (int i = 0; i < M; i++) {  
                for (int j = 0; j < N; j++)  
                     printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');  
           }  
      }  
 }  
 int main()  
 {  
      int T;  
      scanf("%d",&T);  
      for (int t = 1; t <= T; t++) {  
           M = 5;  
           N = 6;  
           for (int i = 0; i < M; i++)  
                for (int j = 0; j < N; j++)  
                     scanf("%d", &tile[i][j]);  
           printf("PUZZLE #%d\n", t);  
           solve();  
      }  
      return 0;  
 }  

POJ.3185 The Water Bowls

1.Problem
http://poj.org/problem?id=3185

2.Idea
Flipping

3.Source

 vector<int> A(20);  
 int solve()  
 {  
      vector<int> a = A;  
      int ans = 0;  
      for (int i = 1; i < 20; i++) {  
           if (a[i - 1] == 1) {  
                //cout << i << endl;  
                a[i - 1] = 1 - a[i - 1];  
                a[i] = 1 - a[i];  
                a[i + 1] = 1 - a[i + 1];  
                ans++;  
           }  
      }  
      return ans;  
 }  
 int main()  
 {  
      for (int i = 0; i < 20; i++) {  
           cin >> A[i];  
      }  
      int ans = solve();  
      reverse(A.begin(), A.end());  
      ans = min(ans, solve());  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3279 Fliptile

1.Problem
http://poj.org/problem?id=3279

2.Idea
Flipping

3.Source

 #define MAX_M 15  
 #define MAX_N 15  
 const int dx[5] = { -1, 0, 0, 0, 1 };  
 const int dy[5] = { 0, -1, 0, 1, 0 };  
 int N, M;  
 int tile[MAX_M][MAX_N];  
 int opt[MAX_M][MAX_N];  
 int flip[MAX_M][MAX_N];  
 int get(int x, int y)  
 {  
      int c = tile[x][y];  
      for (int d = 0; d < 5; d++) {  
           int x2 = x + dx[d], y2 = y + dy[d];  
           if (0 <= x2 && x2 < M && 0 <= y2 && y2 < N) {  
                c += flip[x2][y2];  
           }  
      }  
      return c % 2;  
 }  
 int calc()  
 {  
      for (int i = 1; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                if (get(i - 1, j) != 0) {  
                     flip[i][j] = 1;  
                }  
           }  
      }  
      for (int j = 0; j < N; j++) {  
           if (get(M - 1, j) != 0) return -1;  
      }  
      int res = 0;  
      for (int i = 0; i < M; i++) {  
           for (int j = 0; j < N; j++) {  
                res += flip[i][j];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int res = -1;  
      for (int i = 0; i < 1 << N; i++) {  
           memset(flip, 0, sizeof flip);  
           for (int j = 0; j < N; j++) {  
                flip[0][N - j - 1] = i >> j & 1;  
           }  
           int num = calc();  
           if (num >= 0 && (res < 0 || res > num)) {  
                res = num;  
                memcpy(opt, flip, sizeof(flip));  
           }  
      }  
      if (res < 0) {  
           cout << "IMPOSSIBLE" << endl;  
      }  
      else {  
           for (int i = 0; i < M; i++) {  
                for (int j = 0; j < N; j++)  
                     printf("%d%c", opt[i][j], j + 1 == N ? '\n' : ' ');  
           }  
      }  
 }  
 int main()  
 {  
      cin >> M >> N;  
      for (int i = 0; i < M; i++)  
           for (int j = 0; j < N; j++)  
                cin >> tile[i][j];  
      solve();  
      return 0;  
 }  

POJ.3276 Face The Right Way

1.Problem
http://poj.org/problem?id=3276

2.Idea
Flipping method.

3.Source

 #define MAX_N 5000  
 int N;  
 int dir[MAX_N];  
 int f[MAX_N];  
 int calc(int k)  
 {  
      memset(f, 0, sizeof f);  
      int res = 0;  
      int sum = 0;  
      for (int i = 0; i + k <= N; i++) {  
           if ((dir[i] + sum) % 2) {  
                res++;  
                f[i] = 1;  
           }  
           sum += f[i];  
           if (i - k + 1 >= 0) {  
                sum -= f[i - k + 1];  
           }  
      }  
      //residual  
      for (int i = N - k + 1; i < N; i++) {  
           if ((dir[i] + sum) % 2) return -1;  
           if (i - k + 1 >= 0) {  
                sum -= f[i - k + 1];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int K = 1, M = N;  
      for (int k = 1; k <= N; k++) {  
           int m = calc(k);  
           if (m > 0 && M > m) {  
                M = m;  
                K = k;  
           }  
      }  
      cout << K << " " << M << endl;  
 }  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) {  
           char c;  
           cin >> c;  
           if (c == 'B') dir[i] = 1;  
           else dir[i] = 0;  
      }  
      solve();  
      return 0;  
 }