#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>


typedef struct _WALLS
{
	int nStartx;
	int nStarty;
	
	int nEndx;
	int nEndy;
}WALLS;


void Zeros(int **a,int nRow,int nColumn)
{
	int n,m;
	for(n=0;n<=nRow;n++)/*//m为列,即是x轴*/
	{
		for(m=0;m<=nColumn;m++)/*//n为行,即是y轴*/
		{
			a[n][m]=0;
		}
	}
}

int PointInWhichWalls(WALLS *pWalls,int nWalls ,int n,int m)
{
	int i;
	for(i=0;i<nWalls;i++)
	{
		if( pWalls[i].nStartx<=m && m<=pWalls[i].nEndx && n==pWalls[i].nStarty)
			return i;
	}
	return 0;
}

/*
int GetBadWallIndex(int *pnBadWall,int nWalls,WALLS *pWalls)
{
	int max=0;
	int i;
	int mm=0;
	for(i=0;i<nWalls;i++)
	{
		if (pnBadWall[i]>max)
		{
			max=pnBadWall[i];
			mm=i;
		}
	}
	
	for(i=0;i<nWalls;i++)
	{
		if (pnBadWall[i]==max)
		{
			if( (pWalls[i].nEndx-pWalls[i].nStartx) > (pWalls[mm].nEndx-pWalls[mm].nStartx) ) 
				mm=i;
		}
	}

	return mm;
}
*/

void Sort(int *pnRowWall,int nMaxRow,WALLS *pWalls)
{
	int i,j;
	int tmp;
	for(i=0;i<nMaxRow-1;i++)
	{
		for(j=i+1;j<nMaxRow;j++)
		{
			if( (pnRowWall[i]!=-1) && (pnRowWall[j]!=-1) )
			{			
				if( pWalls[pnRowWall[i]].nEndx < pWalls[pnRowWall[j]].nEndx )
				{
					tmp=pnRowWall[i];
					pnRowWall[i]=pnRowWall[j];
					pnRowWall[j]=tmp;;
				
				}
			}
		}
	}
}

void main()
{
	/*FILE *pf;*/

	int i,j;
	int n,m,m2;

	int tmp;  /*//交换变量*/

	/*//int a[MAX][MAX]={0};*/
	int **a;
	int k;
	int nTime;
	int nWalls;
	WALLS *pWalls;
	int *pnRowWall;

	int nMaxColumn=0;	/*//最大列**/
	int nMaxRow=0;		/*//最大行*/

	int nColumnCount=0;
	int nDesWall;
	int flag=0;
	int nResult=0;

	/*pf=fopen("in.txt","r");
	fscanf(pf,"%d",&nTime);*/
	scanf("%d",&nTime);

	for(i=0;i<nTime;i++)
	{

		/*fscanf(pf,"%d%d\n",&nWalls,&k);*/
		scanf("%d %d\n",&nWalls,&k);
		
		pWalls=(WALLS *)malloc(sizeof(WALLS)*nWalls);
		
		for(j=0;j<nWalls;j++)
		{
			/*fscanf(pf,"%d%d%d%d\n",
				&pWalls[j].nStartx,//x为列
				&pWalls[j].nStarty,//y为行
				&pWalls[j].nEndx,
				&pWalls[j].nEndy);*/
			
			scanf("%d %d %d %d\n",
				&pWalls[j].nStartx,/*//x为列*/
				&pWalls[j].nStarty,/*//y为行*/
				&pWalls[j].nEndx,
				&pWalls[j].nEndy);

			/* 交换起终点 */
			if(pWalls[j].nStartx > pWalls[j].nEndx)
			{
				tmp=pWalls[j].nStartx;
				pWalls[j].nStartx=pWalls[j].nEndx;
				pWalls[j].nEndx=tmp;
			}
			
			if(pWalls[j].nEndx > nMaxColumn)
				nMaxColumn=pWalls[j].nEndx;
			
			if(pWalls[j].nStarty > nMaxRow)
				nMaxRow=pWalls[j].nStarty;
			
		}
		
		pnRowWall=(int *)malloc(sizeof(int)*(nMaxRow+1));
		a=(int **)malloc(sizeof(int *)*(nMaxRow+1));
		for(j=0;j<=nMaxRow;j++)
		{
			a[j]=(int *)malloc(sizeof(int)*(nMaxColumn+1));
			pnRowWall[j]=-1;
		}
		Zeros(a, nMaxRow, nMaxColumn);
		
		for(j=0;j<nWalls;j++)
		{
			for(m=pWalls[j].nStartx;m<=pWalls[j].nEndx;m++)
			{
				a[pWalls[j].nStarty][m]=1;
			}
		}
		
		/*
		//---------------------
		//查看打印值
		printf("\n-------------------\n");
		for(n=0;n<=nMaxRow;n++)
		{
			for(j=0;j<=nMaxColumn;j++)
			{
				printf("%d ",a[n][j]);
			}
			printf("\n");
		}
		//---------------------*/
		
		for(m=0;m<=nMaxColumn;m++)/*//m为列,即是x轴*/
		{
		
			nColumnCount=0;
			for(n=0;n<=nMaxRow;n++)/*//n为行,即是y轴*/
			{
				if(a[n][m]==1)
					nColumnCount++;
			}
			
			if(nColumnCount>k)	/*//循环扫描nColumnCount-k次*/
			{
				j=0;
				flag=1;
				for(n=0;n<=nMaxRow;n++)
				{
					
					if(a[n][m]==1)
					{
						nDesWall=PointInWhichWalls(pWalls,nWalls,n,m);
						pnRowWall[j]=nDesWall;
						j++;
					}
				}
				
				Sort(pnRowWall,j,pWalls);
				
				/*remove nColumnCount-k block walls*/
				for(j=0;j<nColumnCount-k;j++)
				{
					
					for(m2=pWalls[ pnRowWall[j] ].nStartx; m2<=pWalls[ pnRowWall[j] ].nEndx; m2++)
					{
						a[ pWalls[pnRowWall[j]].nStarty ][m2]=0;
					}
					
					/*
					//---------------------
					//查看打印值
					printf("\n-------------------\n");
					for(n=0;n<=nMaxRow;n++)
					{
						for(m2=0;m2<=nMaxColumn;m2++)
						{
							printf("%d ",a[n][m2]);
						}
						printf("\n");
					}
					//---------------------*/

					nResult++;
				}
			}
	
			if(flag)
			{
				flag=0;
				for(j=0;j<nMaxRow;j++)
				{
					pnRowWall[j]=-1;
				}
			}
					
		}		

		printf("%d\n",nResult);
		
		nResult=0;
		
		free(pWalls);
		free(pnRowWall);
		
		for(j=0;j<=nMaxRow;j++)
		{
			free(a[j]);
		}
		free(a);
	}
	
	/*fclose(pf);*/
}


• 这题目很阴,大家注意细节!! (0) try88 2005-06-01 20:00:03
• 怎么还有主动贴代码的。。。 (5056) e_at_fdu 2005-10-18 15:43:18
  • hawk删吧 (0) frkstyc 2005-10-18 15:43:59
    • 这个代码注释的挺详细的，留着吧 (0) TN 2005-10-18 15:45:45
      • 照习惯办吧，之前那个谁过一道贴一道已经让人ft死了 (0) frkstyc 2005-10-18 15:46:53
        • 那个比较搞笑，“我的C代码，简洁” (0) TN 2005-10-18 15:47:25
  • 炫耀白。。。。 (4) bitchen 2011-07-18 11:41:51
• 我晕，这题没有必要这么长吧 (0) liymouse 2005-10-18 16:36:41
• Re:经过啊拉,一天的努力终于搞定着,现在共享我的程序,共大家参考(已经通过) (7) Justtree 2009-03-20 11:34:28