首页 > 其他 > 详细

【stack果然神器】code forces 394C Dominoes

时间:2014-02-23 07:42:55      阅读:313      评论:0      收藏:0      [点我收藏+]

code forces   394C   Dominoes               题目链接:http://codeforces.com/problemset/problem/394/C

bubuko.com,布布扣

题目大意:用一个两位数字组合描述一张多米诺骨牌,这两位数字只可能取0或1,这样骨牌就一共有四种(“00”、“11”、“10”、“01“),给出两个整数m、n代表有m行n列的骨牌,下面给出这组m×n的骨牌排列(两个骨牌之间有一空格)。得到排列后统计每一列有多少个”1“,设num为其最大值,然后打乱重排,目的是使重排后的num最小。

题目分析:

        贪心法。先放11,再放10或01(由于重排时可以旋转180°,所以10和01没有区别),最后放00.

        蛇形排列。排第一、三、五……行时从左向右放,反之从右向左放。

code:

#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
int main()
{
	int m,n,i,j,c00=0,c11=0,c01=0;
	stack<char>s;
	char c[4];
	scanf("%d%d",&m,&n);
	for(i=0;i<n*m;i++)
	{
		scanf("%s",c);
		switch(c[0]+c[1])
		{
			case 96:c00++;break;
			case 97:c01++;break;
			case 98:c11++;
		}
	}
	for(i=0;i<m;i++)
	{
		if(i%2)
		for(j=0;j<n;j++)
		{
			if(c11)
			{
				s.push(j==0?‘\n‘:‘ ‘);
				s.push(‘1‘);
				s.push(‘1‘);
				c11--;
			}
			else if(c01)
			{
				s.push(j==0?‘\n‘:‘ ‘);
				s.push(‘0‘);
				s.push(‘1‘);
				c01--;
			}
			else
			{
				s.push(j==0?‘\n‘:‘ ‘);
				s.push(‘0‘);
				s.push(‘0‘);
			}
		}
		else
		for(j=0;j<n;j++)
		{
			if(c11)
			{
				printf("%s%s","11",j==n-1?"\n":" ");
				c11--;
			}
			else if(c01)
			{
				printf("%s%s",i%2?"10":"01",j==n-1?"\n":" ");
				c01--;
			}
			else printf("%s%s","00",j==n-1?"\n":" ");
		}
		while(!s.empty())printf("%c",s.top()),s.pop();
	}
	return 0;
}
PS:stack果然神器,省了不少代码啊……bubuko.com,布布扣






【stack果然神器】code forces 394C Dominoes

原文:http://blog.csdn.net/blogs_of_slicer/article/details/19688231

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!