Go to diff to previous submission
#include <cstdio> #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <limits.h> #include <map> #include <queue> #include <vector> #include <set> #include <stack> #include <bitset> #include <string> using namespace std; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef set<int> si; typedef set<ii> sii; #define MP make_pair #define PB push_back #define REP(i,a) for ( int i = 0; i < int(a); i++) #define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++) #define FORD(i,a,b) for(int i= int(a); i>=int(b); i--) const int INF = 1<<29; typedef long long int ll; int ar, ac, tr, tc; char board[1001][1001]; int tiles[1001][1001]; int isIn( int r1, int r2, int c1, int c2 ) { int count = 0; r1 = max( r1, 0 ); r2 = min( r2, ar - 1 ); c1 = max( c1, 0 ); c2 = min( c2, ac - 1 ); //printf("%d %d %d %d\n", r1, r2, c1, c2); FOR( i, r1, r2 ) FOR( j, c1, c2 ) if ( board[i][j] == 'X' ) ++count; return count; } void updateTile( int r1, int r2, int c1, int c2, int x, int y ) { r1 = max( r1, 0 ); r2 = min( r2, ar - 1 ); c1 = max( c1, 0 ); c2 = min( c2, ac - 1 ); if ( c1 > 0 ) FOR( i, r1, r2 ) if ( board[i][c1-1] == 'X' ) --tiles[x][y]; if (c2 <=ac-1 ) FOR( i, r1, r2 ) if ( board[i][c2] == 'X' ) ++tiles[x][y]; } void updateTile2( int r1, int r2, int c1, int c2, int x, int y ) { r1 = max( r1, 0 ); r2 = min( r2, ar - 1 ); c1 = max( c1, 0 ); c2 = min( c2, ac - 1 ); if ( c1 >= 0 ) FOR( i, r1, r2 ) if ( board[i][c1] == 'X' ) ++tiles[x][y]; if (c2 <ac-1 ) FOR( i, r1, r2 ) if ( board[i][c2+1] == 'X' ) --tiles[x][y]; } int countTiles( int r, int c, bool left ) { int count = 0; for ( int i = r, i2=0; i < ar; i += tr, i2++ ) { for ( int j = c, j2=0; j < ac; j += tc, j2++ ) { if(!left) updateTile(i,i+tr-1,j,j+tc-1,i2,j2); else updateTile2(i,i+tr-1,j,j+tc-1,i2,j2); if ( tiles[i2][j2] >0 ) ++count; } } return count; } int prepare( int r, int c ) { int sum = 0; int i2 = 0, j2; for ( int i = r; i < ar; i += tr, ++i2 ) { j2 = 0; for ( int j = c; j < ac; j += tc, ++j2 ) { tiles[i2][j2] = isIn( i, i+tr-1, j, j+tc-1 ); if ( tiles[i2][j2] >0 ) sum++; } } return sum; } /* void updateRow(int r){ for (int i2=0 ; r < ar; r += tr, ++i2 ) { for ( int j = -tc+1, j2=0; j < ac; j += tc, ++j2 ) tiles[i2][j2] = c } }*/ int main() { while ( scanf("%d%d%d%d", &ar, &ac, &tr, &tc) == 4 ) { FOR( i, 0, ar-1 ) { FOR( j, 0, ac-1 ) scanf(" %c", &board[i][j]); //scanf("%*c"); } int count = INT_MAX; int tmp; //prepare( -tr+1, -tc+1 ); FOR( i, -tr+1, 0 ) { tmp = prepare(i,-tc+1); count = min( count, tmp ); FOR( j, -tc+2, 0 ) { //if ( i == -tr+1 && j == -tc+1 ) // continue; tmp = countTiles( i, j,0 ); count = min( count, tmp ); //printf("%d-%d\n", tmp, count); } // updateRow(i); /* ++i; if ( i >= 0 ) break; prepare(i,-tc+1); FORD( j, 0, -tc+1 ) { if ( i == -tr+1 && j == -tc+1 ) continue; int tmp = countTiles( i, j,1 ); count = min( count, tmp ); //printf("%d-%d\n", tmp, count); }*/ } printf("%d\n", count); // break; } return 0; }
--- c5.s979.cteam013.fm.cpp.0.fms.cpp +++ c5.s994.cteam013.fm.cpp.0.fms.cpp @@ -101,13 +101,16 @@ } -void prepare( int r, int c ) -{ +int prepare( int r, int c ) +{ int sum = 0; int i2 = 0, j2; for ( int i = r; i < ar; i += tr, ++i2 ) { j2 = 0; - for ( int j = c; j < ac; j += tc, ++j2 ) + for ( int j = c; j < ac; j += tc, ++j2 ) { tiles[i2][j2] = isIn( i, i+tr-1, j, j+tc-1 ); + if ( tiles[i2][j2] >0 ) sum++; + } } + return sum; } /* @@ -132,16 +135,18 @@ } int count = INT_MAX; + int tmp; //prepare( -tr+1, -tc+1 ); FOR( i, -tr+1, 0 ) { - prepare(i,-tc+1); - FOR( j, -tc+1, 0 ) - { - if ( i == -tr+1 && j == -tc+1 ) - continue; - int tmp = countTiles( i, j,0 ); - count = min( count, tmp ); + tmp = prepare(i,-tc+1); + count = min( count, tmp ); + FOR( j, -tc+2, 0 ) + { + //if ( i == -tr+1 && j == -tc+1 ) + // continue; + tmp = countTiles( i, j,0 ); + count = min( count, tmp ); //printf("%d-%d\n", tmp, count); - } + } // updateRow(i); /* ++i;