首页 > 代码库 > ZOJ 3810 - A Volcanic Island （ 构造 ）
ZOJ 3810 - A Volcanic Island （ 构造 ）
ZOJ 3810 - A Volcanic Island （ 构造 ）
题意：
给定一个N*N 的方格，需要用4种颜色进行染色，
要求：划分出N片区域，每片区域用一种颜色，且构造出的区域形状，颜色，旋转后的形状都不能相同
分析：
构造的题目一直都不是很好做，主要是因为自己智商太低。。
这个是看了郏老大的题解才会构造的，至于为什么这样构造。也说不出一个所以然来。
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define MAXN 111#define CLR( a,b ) memset( a, b, sizeof(a) )int g[MAXN][MAXN];char color[] = "RGB";int T, n;void solve(){ CLR( g, -1 ); int col = 1 ,i, j, k, ct; for( i = 0; i < n; ++i ) g[i][n-1] = 0; k = n >> 1; //printf( "k = %d\n", k ); for( i = 0; i < k; ++i ) { if( i & 1 ) { for( j = 0; j < n-1-i; ++j ) g[i][j] = col; int ct = 0; for( j = 0; ct <= i; j++, ct++ ) g[i+1][j] = col; } else { for( j = 0; j < n-1-i; ++j ) g[i][j+i] = col; int ct = 0; for( j = n-2; ct <= i; j--, ct++ ) g[i+1][j] = col; } col++; } if( (k & 1) == 0 ) { for( i = k; i < n; ++i ) { ct = n, j = 0; while( true ) { if( g[i][j] == -1 ) g[i][j] = col, ct--; j++; if( j >= n-1 ) break; } for( j = 0; ct > 0; ++j, ct-- ) g[i+1][j] = col; col++; } swap( g[n-1][0], g[n-3][n-2] ); } else { for( i = k; i < n-1; ++i ) { for( j = 0; j < n-i-1; ++j ) g[i][j] = col; for( --j; j < n-1; ++j ) g[i+1][j] = col; col++; } swap( g[n-1][n-2], g[n-3][0] ); } for( i = 0; i < n; ++i ) { if( i != 0 ) putchar( ‘\n‘ ); for( j = 0; j < n; ++j ) { if( g[i][j] == 0 ) putchar(‘Y‘); else printf( "%c", color[g[i][j] % 3] ); //printf( "%d", g[i][j] ); } } putchar( ‘\n‘ );}void Orz(){ scanf( "%d", &T ); while( T-- ) { scanf( "%d", &n ); if( n == 1 ) puts( "Y"); else if( n <= 4 ) puts( "No solution!" ); else if( n == 5 ) { printf( "RRRRY\n" ); printf( "BGRGY\n" ); printf( "BGGGY\n" ); printf( "BRRRY\n" ); printf( "BBRRY\n" ); } else if( n == 6 ) { printf( "RRRRRY\n" ); printf( "BBBBRY\n" ); printf( "GGGBBY\n" ); printf( "RRGGYY\n" ); printf( "RRGBBY\n" ); printf( "RRBBBB\n" ); } else { solve(); } }}int main(){ Orz(); return 0;}
ZOJ 3810 - A Volcanic Island （ 构造 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。