Pagini recente » Cod sursa (job #1451792) | Profil Sasha_12454 | Cod sursa (job #2648466) | Cod sursa (job #1752785) | Cod sursa (job #125721)
Cod sursa(job #125721)
#include <cstdio>
int dp[511][511], id;
short U[511][511];
char type[511][511];
void rec( int x, int y, int offX, int offY )
{
if( x == 0 || y == 0 )
return;
++id;
printf("%d %d -> %d\n", x, y, U[x][y] );
for( int i = x + offX - 1; i >= x + offX - U[x][y]; i-- )
for( int j = y + offY - 1; j >= y + offY - U[x][y]; j-- )
dp[i][j] = id;
if( type[x][y] == 'L' )
rec( x, y - U[x][y], offX, offY ),
rec( x - U[x][y], U[x][y], offX, offY + ( y - U[x][y] ) );
if( type[x][y] == 'U' )
rec( U[x][y], y - U[x][y], offX + ( x - U[x][y] ), offY ),
rec( x - U[x][y], y, offX, offY );
}
int main()
{
freopen("piese.in", "r", stdin);
freopen("piese.out", "w", stdout);
int N, M;
scanf("%d %d", &N, &M);
for( int i = 1; i <= N; i++ )
for( int j = 1; j <= M; j++ )
dp[i][j] = i * j,
U[i][j] = 1,
type[i][j] = 'L';
for( int at = 2; at <= ( N <? M ); at *= 2 )
for( int i = 1; i <= N; i++ ) if( at <= i )
for( int j = 1; j <= M; j++ ) if( at <= j )
{
if ( 1+dp[i][j-at]+dp[i-at][at] < dp[i][j] )
{
dp[i][j] = 1+dp[i][j-at]+dp[i-at][at];
U[i][j] = at;
type[i][j] = 'L';
}
if (1+dp[at][j-at] + dp[i-at][j] < dp[i][j] )
{
dp[i][j] = 1+dp[at][j-at]+dp[i-at][j];
U[i][j] = at;
type[i][j] = 'U';
}
}
printf("%d\n", dp[N][M] );
rec( N, M, 1, 1 );
for( int i = 1; i <= N; i++ )
{
printf("%d", dp[i][1] );
for( int j = 2; j <= M; j++ )
printf(" %d", dp[i][j] );
printf("\n");
}
return 0;
}