oj.uz

Submission #135835

# Submission time Handle Problem Language Result Execution time Memory
135835 2019-07-24T12:04:51 Z model_code Connect (CEOI06_connect) C++
100 / 100
 31 ms 7928 KB 
#include <cstdio>
#include <cstring>

using namespace std;

#define MAXN 12
#define MAXM 39

int n, m;
char a[2*MAXN+1][2*MAXM+10];
int how[MAXN][MAXM];
short memo[MAXN][MAXM][1<<MAXN][2];
const short inf = 10000;

const char *b[3][11] = {
   { "+ +", "+ +", "+.+", "+ +", "+ +", "+ +", "+.+", "+.+", "+.+", "+ +", "+ +" },
   { "   ", ".X ", " X ", " X.", " X ", "...", " . ", ".. ", " ..", " ..", ".. " },
   { "+ +", "+ +", "+ +", "+ +", "+.+", "+ +", "+.+", "+ +", "+ +", "+.+", "+.+" },
};

short rec( int r, int c, int mask, int U, int reconstruct ) {
   if( r == n ) return rec( 0, c+1, mask, 0, reconstruct );
   if( c == m ) return 0;

   short &ret = memo[r][c][mask][U];
   if( !reconstruct && ret >= 0 ) return ret;

   ret = inf;

   int L = (mask>>r)&1;
   int R = a[2*r+1][2*c+2] == ' ';
   int D = a[2*r+2][2*c+1] == ' ';
   int X = a[2*r+1][2*c+1] == 'X';

   int h0=0, h1=0, h2=0, h3=0;

   #define tst(t0,t1,t2,t3) { \
      int v = t1 + rec( r+1, c, t2, t3, 0 ); \
      if( v < ret ) { ret = v; h0=t0; h1=t1; h2=t2; h3=t3; } \
   }

   if( !X && !L && !U && 1 && 1 ) tst(  0, 0, mask & ~(1<<r), 0 ); // empty

   if(  X &&  L && !U && 1 && 1 ) tst(  1, 1, mask & ~(1<<r), 0 ); // left
   if(  X && !L &&  U && 1 && 1 ) tst(  2, 1, mask & ~(1<<r), 0 ); // up
   if(  X && !L && !U && R && 1 ) tst(  3, 1, mask |  (1<<r), 0 ); // right
   if(  X && !L && !U && 1 && D ) tst(  4, 1, mask & ~(1<<r), 1 ); // down

   if( !X &&  L && !U && R && 1 ) tst(  5, 2, mask |  (1<<r), 0 ); // left-right
   if( !X && !L &&  U && 1 && D ) tst(  6, 2, mask & ~(1<<r), 1 ); // up-down

   if( !X &&  L &&  U && 1 && 1 ) tst(  7, 2, mask & ~(1<<r), 0 ); // left-up
   if( !X && !L &&  U && R && 1 ) tst(  8, 2, mask |  (1<<r), 0 ); // up-right
   if( !X && !L && !U && R && D ) tst(  9, 2, mask |  (1<<r), 1 ); // right-down
   if( !X &&  L && !U && 1 && D ) tst( 10, 2, mask & ~(1<<r), 1 ); // down-left

   if( reconstruct ) {
      how[r][c] = h0;
      rec( r+1, c, h2, h3, 1 );
   }

   return ret;
}

int main( void ) {
   scanf( "%d%d ", &n, &m );
   for( int r = 0; r < n; ++r ) {
     fgets( a[r], 90, stdin );
     int l = strlen(a[r]);
     while(a[r][l-1] == '\r' || a[r][l-1] == '\n') a[r][l-1] = 0;
   }
   n /= 2; m /= 2;

   memset( memo, -1, sizeof memo );
   printf( "%d\n", rec( 0, 0, 0, 0, 1 ) );

   for( int r = 0; r < n; ++r )
      for( int c = 0; c < m; ++c )
         for( int dr = 0; dr < 3; ++dr )
            for( int dc = 0; dc < 3; ++dc )
               if( b[dr][how[r][c]][dc] != ' ' )
                  a[2*r+dr][2*c+dc] = b[dr][how[r][c]][dc];

   for( int r = 0; r <= 2*n; ++r ) puts( a[r] );
   return 0;
}

Compilation message

connect.cpp: In function 'short int rec(int, int, int, int, int)':
connect.cpp:35:14: warning: variable 'h1' set but not used [-Wunused-but-set-variable]
    int h0=0, h1=0, h2=0, h3=0;
              ^~
connect.cpp: In function 'int main()':
connect.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d%d ", &n, &m );
    ~~~~~^~~~~~~~~~~~~~~~~~~
connect.cpp:68:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
      fgets( a[r], 90, stdin );
      ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7800 KB Output is correct
2 Correct 8 ms 7800 KB Output is correct
3 Correct 8 ms 7800 KB Output is correct
4 Correct 8 ms 7800 KB Output is correct
5 Correct 11 ms 7800 KB Output is correct
6 Correct 8 ms 7800 KB Output is correct
7 Correct 8 ms 7800 KB Output is correct
8 Correct 8 ms 7800 KB Output is correct
9 Correct 8 ms 7800 KB Output is correct
10 Correct 9 ms 7896 KB Output is correct
11 Correct 9 ms 7804 KB Output is correct
12 Correct 10 ms 7800 KB Output is correct
13 Correct 10 ms 7800 KB Output is correct
14 Correct 8 ms 7928 KB Output is correct
15 Correct 8 ms 7804 KB Output is correct
16 Correct 8 ms 7928 KB Output is correct
17 Correct 9 ms 7800 KB Output is correct
18 Correct 9 ms 7928 KB Output is correct
19 Correct 31 ms 7928 KB Output is correct
20 Correct 13 ms 7928 KB Output is correct