2438441_ac_0ms_40k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>
using namespace std;
int n, w, b, he[11], p[11], q;
int i, j, h, H, t[11], T[11], tt, max;
char tmp[11][11];
bool cmp(int a,int b)
{
	return t[a]>t[b];
}

int main()
{
	while(scanf("%d%d%d",&n,&w,&b)==3)
	{
		if(!n&&!w&&!b)
			break;
		H = 0;
		while(n--)
		{
			scanf("%d",&h);
			for(j = 0; j < h; j++)
				scanf("%s",tmp[j]);
			if(!H)
			{
				max = -1;
				for(j = 0; j < w; j++)
				{
					for(i = 0; i < h; i++)
						if(tmp[i][j]=='X')
							break;
					he[j] = h-i;
					if(he[j]>max)
						max = he[j];
				}
				H = h;
			}
			else
			{
				for(j = 0; j < w; j++)
				{
					for(i = h-1; i >= 0; i--)
						if(tmp[i][j]=='X')
							break;
					t[j] = i+1;
					for(i = 0; i < h; i++)
						if(tmp[i][j]=='X')
							break;
					T[j] = h-i;
				}
				for(j = 0; j < w; j++)
					p[j] = j;
				sort(p,p+w,cmp);
				for(i = 0; i < w; i++)
				{
					tt = he[p[i]]+t[p[i]];
					for(j = 0; j < w; j++)
						if(he[p[j]]+t[p[j]]>tt)
							goto con;
					if(tt>b)
					{
						printf("%d ",max);
						max = -1;
						for(j = 0; j < w; j++)
						{
							for(q = 0; q < h; q++)
								if(tmp[q][j]=='X')
									break;
							he[j] = h-q;
							if(he[j]>max)
								max = he[j];
						}
						H = h;
					}
					else
					{
						q = H;h = H+h-tt;H = tt;max = tt;
						for(j = 0; j < w; j++)
							he[j] = q+T[j]-h;
					}
					break;
con:
					;
				}
			}	
		}
		printf("%d\n",max);
	}
	return 1;
}