1002.txt

在这个题目中

#include <stdio.h>

void value(int Blank[][4],int Counter[][4],int n);
void bubble_sort(struct node Box[],int n);
void locate(struct node Box[],int blank[][4],int n);


struct node
{
	int x;
	int y;
	int elem;
	int countervalue;
};

void main()
{
	struct node box[4*4];
	int blank[4][4],counter[4][4];
	int n;
	char string[4][4];
	int i,j;
	char *p;
	int contain2number=0;
	int nn;
	scanf("%d",&n);
	nn = n;
	if(n==0) return;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			blank[i][j] = 0;     //0代表不是墙
		}
	}

	for(i=0;i<n;i++)
	{
		p=string[i];
		scanf("%s",p);
	}
	n = nn;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(string[i][j] == '.') continue;
			else
			{
				if(string[i][j] == 'x')
				{
					blank[i][j] = 1;    //1代表墙
				}
			}
		}
	}

	value(blank,counter,n);

	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			box[i*n+j].x = i;
			box[i*n+j].y = j;
			box[i*n+j].elem = blank[i][j];
			box[i*n+j].countervalue = counter[i][j];
		}
	}

	bubble_sort(box,n*n);
	locate(box,blank,n);

	for(i=0;i<n;i++)    //计算由多少个防火装置（blank[][]＝＝2）
	{
		for(j=0;j<n;j++)
		{
			if(blank[i][j] == 2) contain2number++;
		}
	}

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

/*	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%d",blank[i][j]);
		}
		printf("\n");
	}
*/   //注释掉的部分用于打印出安放好防火装置后的地图
 }

void locate(struct node box[],int blank[][4],int n)  //该函数用来搜索某位置所在行和列，判断是否可以安放防火装置
{
	int i=0;
	int tempiadd,tempjadd,judge=1;
	while(i < n*n)     //i的范围还能更小，即循环的次数还能更少，前？个可以安放fir net的位置,就是说不是墙就行
	{
		tempiadd=0;tempjadd=0;
		while(box[i].x+tempiadd < n && blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] != 1 && judge == 1)
		{			
			if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 0)
			{
				tempiadd++;
			}
			else if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 2) judge = 0;
		}
		tempiadd=0;tempjadd=0;
		while(box[i].x+tempiadd >=0 && blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] != 1 && judge == 1)
		{
			if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 0)
			{
				tempiadd--;
			}
			else if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 2) judge = 0;
		}
		tempiadd=0;tempjadd=0;
		while(box[i].y+tempjadd < n && blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] != 1 && judge == 1)
		{
			if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 0)
			{
				tempjadd++;
			}
			else if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 2) judge = 0;
		}
		tempiadd=0;tempjadd=0;
		while(box[i].y+tempjadd >= 0 && blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] != 1 && judge == 1)
		{
			if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 0)
			{
				tempjadd--;
			}
			else if(blank[ box[i].x+tempiadd ][ box[i].y+tempjadd ] == 2) judge = 0;
		}
		if(judge == 1 && blank[ box[i].x ][ box[i].y ] != 1) blank[ box[i].x ][ box[i].y ] = 2;
		i++;
		judge = 1;
	}
}

void value(int Blank[][4],int Counter[][4],int n)  //该函数用来计算每个位置的权值（权值：解释在下）
{
	int k,tempi,tempj;
	int i,j;
	k = 0;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(Blank[i][j] == 1) 
			{
				Counter[i][j] = 8;				//墙的权值赋为8，优先权最低
				continue;
			}
			else 
			{
				tempi = i+1;					
				while(tempi<n && Blank[tempi][j] == 0) 
				{
					tempi++;
					k++;
				}
				tempi = i-1;
				while(tempi>=0 && Blank[tempi][j] == 0)
				{
					tempi--;
					k++;
				}
				tempj = j+1;
				while(tempj<n && Blank[i][tempj] == 0)
				{
					tempj++;
					k++;
				}
				tempj = j-1;
				while(tempj>=0 && Blank[i][tempj] == 0)
				{
					tempj--;
					k++;
				}
			}
			Counter[i][j] = k;
			k = 0;
		}
	}
}


void bubble_sort(struct node Box[],int n)  //冒泡排序，用于排出权值的高低
{
	int i,j;
	struct node temp;
	int change;
	for(i=n-1,change=1;i>=1 && change;i--)
	{
		change = 0;
		for(j=0;j<i;j++)
		{
			if(Box[j].countervalue > Box[j+1].countervalue)
			{
				temp = Box[j];
				Box[j] = Box[j+1];
				Box[j+1] = temp;
				change = 1;
			}
		}
	}
}

报告：
//在这个题目中，我用了一个权值的方法来判断怎样安放防火装置可以符合题目的要求
//每一个位置有一个权值，该权值表示这个位置所占有的行和列中有效的元素个数，有效即是指若由墙隔开，则
//墙以及墙以外的位置不包括在内
//则可知权值数值越低，即这个位置所占有的行和列中有效的元素个数越少，那么该位置最适合放置防火装置，
//因此，将权值排序，得到安放防火装置的位置优先排列，按照该排列安放防火装置，并用locate函数判断该位置
//所在行和列的有效位置是否已经安放过防火装置，若已经安放过，则放弃放置
//以2代表防火装置，最后计算地图位置属性值为2的元素个数，即为所求
//算法中还有许多可以改进的地方