1006_wa.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

	//找到一个框框之后，把它拿掉，被它覆盖的地方标上?。?可以代表任何东西。当我们只剩下?和.的时候，工作完成！
// hint : all frame are square  x == y;
#include <iostream>

using namespace std;
const int maxX = 50;
const int maxY = 20;
const char c1 = 218 , c2 = 191, c3 = 192, c4 = 217, cv = 179, ch = 196, any = '?';	//提交的时候注意要改
char map[maxY + 1][maxX + 1];
int l[maxY + 1][maxX + 1], u[maxY + 1][maxX + 1], r[maxY + 1][maxX + 1], d[maxY + 1][maxX + 1], hc[maxY + 1][maxX + 1], vc[maxY + 1][maxX + 1];									// hc vc 用来确保得到的frame中不全是问号
										// 如果成功，必须实验－1的情形
int ans[2000][3];
int cnt;
int totS;	// total sybol

int min(int a, int b){ return a<b?a:b; }
void readIn()
{
	int i, j;
//	char c;
	totS = 0;
	for( j = 1; j <= maxY; j++ )
	{
		for( i = 1; i <= maxX; i++ )
		{
			cin >> map[j][i];
			if( map[j][i] != '.' ) totS++;
		}
//		cin >> c;
	}
}

void preCalc()
{
	int i, j;
//	memset( l,0,sizeof(l) );
//	memset( u,0,sizeof(u) );
//	memset( r,0,sizeof(r) );
//	memset( d,0,sizeof(d) );
//	memset( hc,0,sizeof(hc) );
//	memset( vc,0,sizeof(vc) );
	
	for( j = 1; j <= maxY; j++ )
		for(i = 1; i <= maxX; i++)
		{
			if( map[j][i] != '.' && map[j][i] != any )
				hc[j][i] = hc[j][i - 1] + 1, vc[j][i] = vc[j - 1][i] + 1;
			else
				hc[j][i] = hc[j][i - 1], vc[j][i] = vc[j - 1][i];
			
			if( map[j][i] == c1 || map[j][i] == c3 )
				l[j][i] = i;
			if( map[j][i] == c2 || map[j][i] == c4 || map[j][i] == ch || map[j][i] == any )
				if( map[j][i - 1] == c1 || map[j][i - 1] == c3 || map[j][i - 1] == ch || map[j][i - 1] == any ) l[j][i] = l[j][i-1];
				else l[j][i] = i;

			if( map[j][i] == c1 || map[j][i] == c2 )
				u[j][i] = j;
			if( map[j][i] == c3 || map[j][i] == c4 || map[j][i] == cv || map[j][i] == any )
				if( map[j - 1][i] == c1 || map[j - 1][i] == c2 || map[j - 1][i] == cv || map[j - 1][i] == any ) u[j][i] = u[j - 1][i];
				else u[j][i] = j;
						
		} 
		
	for( j = maxY; j >= 1; j-- )
		for( i = maxX; i >=1; i-- )
		{
			if( map[j][i] == c2 || map[j][i] == c4 )
				r[j][i] = i;
			if( map[j][i] == c1 || map[j][i] == c3 || map[j][i] == ch || map[j][i] == any )
				if( map[j][i + 1] == c2 || map[j][i + 1] == c4 || map[j][i + 1] == ch || map[j][i + 1] == any ) r[j][i] = r[j][i+1];
				else r[j][i] = i;
		
			if( map[j][i] == c3 || map[j][i] == c4 )
				d[j][i] = j;
			if( map[j][i] == c1 || map[j][i] == c2 || map[j][i] == cv || map[j][i] == any )
				if( map[j + 1][i] == c3 || map[j + 1][i] == c4 || map[j + 1][i] == cv || map[j + 1][i] == any ) d[j][i] = d[j + 1][i];
				else d[j][i] = j;	
		}
	
}

void clear( int x, int y )
{
	if( map[y][x] != '.' && map[y][x] != any ) 
		{totS--;	map[y][x] = any;}
}
bool setans( int a, int b, int c )
{
	int i;
	int t = totS;
	for( i = a; i <= a+c; i++ )
		{clear(i, b); clear(i, b+c);} 
	for( i = b+1; i<= b+c-1; i++ )
		{clear(a, i); clear(a+c, i);}
	if(totS == t)
		return false;
	else
	{
		cnt++;
		ans[cnt][0] = b-1, ans[cnt][1] = a-1, ans[cnt][2]= c+1;
		return true;
	}
}
void search()
{
	int i, j, k;
	for( i = 1; i <= maxX-1; i++ )
		for( j = 1; j <= maxY-1; j++)
		{
			if( map[j][i] == c1 || map[j][i] == any )
			{
				int range = min( r[j][i] - i, d[j][i] - j );
				for( k = range; k >= 1; k-- )
					if((map[j][i + k] == c2 || map[j][i + k] == any) &&
						(map[j + k][i] == c3 || map[j + k][i] == any) &&
						(map[j+k][i+k] == c4 || map[j+k][i+k] == any) &&
						u[j+k][i+k] <= j && l[j+k][i+k] <= i &&
						(( vc[j+k][i] > vc[j-1][i] ) || ( hc[j][i+k] > hc[j][i-1] ))
					 )if( setans( i, j, k ) )return;
			}
		}
} 

void output()
{
	int i;
	cout << cnt << endl;
	for( i = cnt; i >= 1; i-- )
		cout << ans[i][1] << " " << ans[i][0] << " " << ans[i][2] <<endl;
}
int main()
{
//	freopen("1006.in","r",stdin);
	readIn();
	while( totS > 0 )
	{
		preCalc();
		search();
	}
	output();
	return 0;
}