> 
> #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);*/
> }
> 

• 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