fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1010;
  4. const int NONE = 0;
  5. const int HAS_BACK = 1;
  6. const int HAS_BACK_USED = 2;
  7.  
  8. char mat[2][MAX];
  9. int n;
  10. int dp[MAX][3][3]; // pos, top row state, bottom row state
  11.  
  12. int Go(int pos, int st0, int st1) {
  13.   if (pos == n)
  14.     return 0;
  15.   int& ret = dp[pos][st0][st1];
  16.   int cost, new_state;
  17.   if (ret == -1) {
  18.     ret = 1 << 30;
  19.     if (mat[0][pos] == 'X') {
  20.       if (mat[1][pos] == 'X') {
  21.         ret = Go(pos+1, NONE, NONE);
  22.       } else {
  23.         if (st1 == NONE) {
  24.           new_state = HAS_BACK;
  25.           cost = 1;
  26.         } else {
  27.           new_state = st1;
  28.           cost = 0;
  29.         }
  30.         ret = cost + Go(pos+1, NONE, new_state);
  31.       }
  32.     } else {
  33.       if (mat[1][pos] == 'X') {
  34.         if (st0 == NONE) {
  35.           new_state = HAS_BACK;
  36.           cost = 1;
  37.         } else {
  38.           new_state = st0;
  39.           cost = 0;
  40.         }
  41.         ret = cost + Go(pos+1, new_state, NONE);
  42.       } else {
  43.         // both free squares.
  44.         if (st0 != NONE && st1 != NONE) {
  45.           ret = Go(pos+1, st0, st1);
  46.         } else if (st0 == NONE && st1 == NONE) {
  47.           // put on top row or bottom row
  48.           ret = 1 + min(Go(pos+1, HAS_BACK_USED, NONE), Go(pos+1, NONE, HAS_BACK_USED));
  49.         } else if (st0 != NONE) {
  50.           if (st0 == HAS_BACK)
  51.             ret = Go(pos+1, HAS_BACK_USED, NONE);
  52.           ret = min(ret, 1 + Go(pos+1, st0, HAS_BACK));
  53.         } else {
  54.           if (st1 == HAS_BACK)
  55.             ret = Go(pos+1, NONE, HAS_BACK_USED);
  56.           ret = min(ret, 1 + Go(pos+1, HAS_BACK, st1));
  57.         }
  58.       }
  59.     }
  60.   }
  61.   return ret;
  62. }
  63. int Solve() {
  64.   scanf("%d %s %s", &n, mat[0], mat[1]);
  65.   memset(dp, -1, sizeof dp);
  66.   return Go(0, NONE, NONE);
  67. }
  68.  
  69. int main() {
  70.   int ntests;
  71.   scanf("%d", &ntests);
  72.   for (int nt = 1; nt <= ntests; ++nt) {
  73.     printf("Case #%d: %d\n", nt, Solve());
  74.   }
  75.   return 0;
  76. }
  77.  
Success #stdin #stdout 0s 3448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Q1ebEu
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!