Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 经过啊拉,一天的努力终于搞定着,现在共享我的程序,共大家参考(已经通过)

Posted by try88 at 2005-06-01 19:58:53 on Problem 1230
```#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 max=0;
int i;
int mm=0;
for(i=0;i<nWalls;i++)
{
{
mm=i;
}
}

for(i=0;i<nWalls;i++)
{
{
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);*/
}
```

Followed by: