题解 P6428 【[COCI2008-2009#1] MRAVOJED】
wuyonghuming · · 题解
思路：
这道题目是个枚举。
一开始要找到第一个建筑的左上角的点，作为输出的前两个数，否则只能用后面的点，但是后面的点形成的正方形一定不会包括这个点，所以必须把这个点作为前两个数的输出。
找到了这个点之后，我们要计算它的边长，就从这个点的长度进行枚举，如果能长，当然越长越好，可以为把填满建筑格子的概率增大。如果在查找的时候遇到非建筑格子，那么现在就可以输出长度了，接着再弄一个数组记录已经去掉第一个建筑的地图。
接下来的第二个点要从后往前找，然后枚举长度，像找第一个点那样枚举，如果在长度达到最大，依旧没有填满建筑格子，那么这个点就不行了，注意一定要尽量大，否则上面会有点没有包括在正方形内，所以要到最大的时候再输出长度，可以节省效率。
代码:
#include <bits/stdc++.h>//万能的头文件
using namespace std;
char s[111][111],l[111][111];//s是地图，l是去掉第一个建筑的地图
int main()//主函数
{
int r,c;//是长和宽
cin>>r>>c;//输入
for(int i=1;i<=r;i++)//有r行
{
for(int j=1;j<=c;j++)//有c列
{
cin>>s[i][j];//输入地图
}
}
bool p=false;//先认为没有找到第一个建筑，让它一直循环
for(int i=1;i<=r;i++)//有r行
{
for(int j=1;j<=c;j++)//有c列,枚举每个点
{
if(s[i][j]=='x')//如果是建筑的格子
{
printf("%d %d ",i,j);//一定是左上角的点，输出
int k;//这个是用来计算正方形的边长
for(k=1;i+k-1<=r||j+k-1<=r;k++)//枚举边长，越长越好
{
for(int u=i;u<=i+k;u++)//从这个点的x坐标开始，继续k个点
{
for(int v=j;v<=j+k;v++)//从这个点的y坐标开始，继续k个点
{
if(s[u][v]!='x')//如果找到了非建筑格子的点那么k就是正方形的边长
{
printf("%d\n",k);//输出长度
for(int a=1;a<=r;a++)//循环长度
{
for(int b=1;b<=c;b++)//循环宽度
{
l[a][b]=s[a][b];//把地图复制到将要去掉第一个建筑的地图
}
}
for(int a=i;a<=i+k-1;a++)//从左上角的x坐标的开始的k个点
{
for(int b=j;b<=j+k-1;b++)//从左上角的y坐标的开始的k个点
{
l[a][b]='.';//把这些点清除
}
}
p=true;//找到了第一个点
break;//跳出循环
}
}
if(p==true)//如果找到了第一个点
{
break;//跳出循环
}
}
if(p==true)//如果找到了第一个点
{
break;//跳出循环
}
}
if(p==true)//如果找到了第一个点
{
break;//跳出循环
}
}
if(p==true)//如果找到了第一个点
{
break;//跳出循环
}
}
if(p==true)//如果找到了第一个点
{
break;//跳出循环
}
}
for(int i=r;i>=1;i--)//从最后一个点开始往前找
{
for(int j=c;j>=1;j--)//从最后一个点开始往前找
{
if(s[i][j]=='x')//如果找到了有建筑的点，包括建筑一
{
int k;//这依旧是正方形的边长
for(k=1;k<=i&&k<=j;k++)//枚举k的边长
{
for(int u=i-k;u<=i;u++)//从i-k的那个点开始因为那才是左上角的点
{
for(int v=j-k;v<=j;v++)//从j-k的那个点开始因为那才是左上角的点
{
if(s[u][v]!='x')//如果这个点不是建筑
{
char t[111][111];//这个数组是判断方案是否可行的
p=true;//先是认为可以
memcpy(t,l,sizeof(t));//把去掉第一个建筑的值赋给用来判断的数组
for(int a=i-k+1;a<=i;a++)//先判断是否占用了不是建筑的点，从左上角开始
{
for(int b=j-k+1;b<=j;b++)//先判断是否占用了不是建筑的点，从左上角开始
{
if(s[a][b]=='.')//如果不是建筑
{
p=false;//方案不可行
break;//跳出循环
}
t[a][b]='.';//把这个点改成平地方便后面判断
}
if(p==false)//如果方案不可行
{
break;//跳出循环
}
}
if(p==false)//如果方案不行
{
continue;//继续找
}
for(int a=1;a<=r;a++)//从第一个点到最后一个点寻找是否有去掉两个建筑后依旧有建筑覆盖的点
{
for(int b=1;b<=c;b++)//从第一个点到最后一个点寻找是否有去掉两个建筑后依旧有建筑覆盖的点
{
if(t[a][b]=='x')//找到了建筑
{
p=false;//方案不可行
break;//跳出循环
}
}
if(p==false)//如果方案不可行
{
break;//跳出循环
}
}
if(p==true)//方案可行
{
printf("%d %d %d",i-k+1,j-k+1,k);//输出边长
return 0;//结束程序
}
}
}
}
}
}
}
}
return 0;//尽管一定已经在上面的循环中结束了，但还是要写的，养成好习惯
} 感谢：
谢谢管理审核！
谢谢大家观赏！