#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;
}


int main()
{

	int i,j;
	int n,m;

	int tmp;

	int **a;
	int k;
	int nTime;
	int nWalls;
	WALLS *pWalls;
	int *pnBadWall;
	
	/* int *pnResult; */

	int nMaxColumn=0;
	int nMaxRow=0;

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

	int nResult=0;
	
	
	/* 输入循环次数 */	
	scanf("%d",&nTime);
/*	pnResult=(int *)malloc(sizeof(int)*nTime); 
	for(i=0;i<nTime;i++)
	{
		pnResult[i]=0;
	}
*/
	for(i=0;i<nTime;i++)
	{
		scanf("%d %d",&nWalls,&k);

		pWalls=(WALLS *)malloc(sizeof(WALLS)*nWalls);
		pnBadWall=(int *)malloc(sizeof(int)*nWalls);

		/* 输入围墙 */
		for(j=0;j<nWalls;j++)
		{
			scanf("%d %d %d %d",
				&pWalls[j].nStartx,
				&pWalls[j].nStarty,
				&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;

			pnBadWall[j]=0;
		}
		
		/* 动态构造平面图 */
		a=(int **)malloc(sizeof(int *)*(nMaxRow+1));
		for(j=0;j<=nMaxRow;j++)
		{
			a[j]=(int *)malloc(sizeof(int)*(nMaxColumn+1));
		}
		/* 初始化平面图为0 */
		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;
			}
		}

		do 
		{			
			flag=0;

			/*-------------------------------------------
			 查看打印值 
			printf("\n-------------------\n");
			for(n=0;n<=nMaxRow;n++)
			{
				for(m=0;m<=nMaxColumn;m++)
				{
					printf("%d ",a[n][m]);
				}
				printf("\n");
			}
			-------------------------------------------*/
			
			/* 逐列循环扫面墙数 */
			for(m=0;m<=nMaxColumn;m++)
			{
				nColumnCount=0;
				for(n=0;n<=nMaxRow;n++)
				{
					if(a[n][m]==1)
						nColumnCount++;
				}
				
				/* 如墙数大于传墙能力k */
				if(nColumnCount>k)
				{
					/* 记录下次要循环再扫描 */
					flag=1;

					for(n=0;n<=nMaxRow;n++)
					{
						if(a[n][m]==1)
						{
							/* 找出墙点所在的墙块 */
							/* 记录撞墙的次数的数组++ */
							nDesWall=PointInWhichWalls(pWalls,nWalls,n,m);
							pnBadWall[nDesWall]++;
						}
					}				
				}
				else if(flag!=1)
				{
					flag=0;
				}
			}

			if(flag==1)
			{
				/* 找出被撞的最多的那块墙 */
				nDesWall=GetBadWallIndex(pnBadWall,nWalls,pWalls);
				
				/* 在平面图上把墙去掉 */
				for(m=pWalls[nDesWall].nStartx; m<=pWalls[nDesWall].nEndx; m++)
                {
					a[ pWalls[nDesWall].nStarty ][m]=0;
				}
				
				/* 记录撞墙的数组重新初始化为0 */
				for(j=0;j<nWalls;j++)
				{
					pnBadWall[j]=0;
				}

				nResult++;
				/*pnResult[i]++;*/
			}		
		
		} while(flag);

		printf("%d\n",nResult); 

		nResult=0;
		
		Zeros(a, nMaxRow, nMaxColumn);
		free(pWalls);
		free(pnBadWall);
		
		for(j=0;j<=nMaxRow;j++)
		{
			free(a[j]);
		}
		free(a);
	}
	
	/*
	for(i=0;i<nTime;i++)
	{
		printf("%d\n",pnResult[i]);
	}
	free(pnResult);*/

	return 0;
}

• 参考前面的discuss (4491) frkstyc 2005-05-31 18:36:55