堡垒问题（贪心） 解题报告

描述：

城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。

输入：

每个测例以一个整数n（1<=n<=4）开始，表示城堡的大小。接下来是n行字符每行n个，‘X’表示该位置是墙，‘.’表示该位置是空格。n等于0标志输入结束。

输出：

每个测例在单独的一行输出一个整数：最多修建堡垒的个数。

输入样例：

4

.X..

....

XX..

....

2

XX

.X

3

.X.

X.X

.X.

3

...

.XX

.XX

4

....

....

....

....

0

输出样例：

5

1

5

2

4

解题思路：首先用贪心，现在X的附近布满，然后扫描一遍，去掉不符合，增加符合条件的，对此计数即可。主要是对数据的处理。

代码如下：

#include<iostream>

usingnamespacestd;
intManage_Data(intn);

chardata[4][4];

intmain()
{

intn;
cin>>n;
while(n)
{
for(inti=0;i<n;i++)
{
for(intj=0;j<n;j++)
cin>>data[i][j];
}
cout<<Manage_Data(n)<<endl;
cin>>n;
}
return0;
}

intManage_Data(intn)
{
for(inti=0;i<n;i++)//先在X的附近放
{
for(intj=0;j<n;j++)
{
if(data[i][j]=='X')
{
if(i>0&&data[i-1][j]!='X')
data[i-1][j]='y';
if(i<n-1&&data[i+1][j]!='X')
data[i+1][j]='y';
if(j>0&&data[i][j-1]!='X')
data[i][j-1]='y';
if(j<n-1&&data[i][j+1]!='X')
data[i][j+1]='y';
}
}
}
intsum=0;
for(i=0;i<n;i++)//扫描，去掉不符合条件的，增加符合条件的
{
for(intj=0;j<n;j++)
{
intstate=0;
if(data[i][j]=='y')
{
for(signedintstep=i-1;step>=0;step--)
{
if(data[step][j]=='y')
{
state=1;
break;
}
elseif(data[step][j]=='X')
break;
}
for(step=j-1;step>=0;step--)
{
if(data[i][step]=='y')
{
state=1;
break;
}
elseif(data[i][step]=='X')
break;
}
if(state==0)
sum++;
else
data[i][j]='.';
}
elseif(data[i][j]=='.')
{
for(signedintstep=i-1;step>=0;step--)
{
if(data[step][j]=='y')
{
state=1;
break;
}
elseif(data[step][j]=='X')
break;
}
for(step=i+1;step<n;step++)
{
if(data[step][j]=='y')
{
state=1;
break;
}
elseif(data[step][j]=='X')
break;
}
for(step=j-1;step>=0;step--)
{
if(data[i][step]=='y')
{
state=1;
break;
}
elseif(data[i][step]=='X')
break;
}
for(step=j+1;step<n;step++)
{
if(data[i][step]=='y')
{
state=1;
break;
}
elseif(data[i][step]=='X')
break;
}
if(state==0)
{
sum++;
data[i][j]='y';
}
}
}
}
returnsum;
}