思想: 深搜DFS
map数组存地图 vis数组记录访问状态 ans数组存每个坐标投放指数
由于安全点不一定连续 可能出现一个安全点4个方向都被暗礁包围 所以要在循环中判断 进行多次深搜
重点: 投放指数计算
求出一个点4个方向连续的安全点个数是必要的 将4个值存好备用c1,c2,l1,l2
判断横竖方向上是否摆的下战舰 即c1+c2>=k?
若满足 则考虑可以摆放的战舰数
我们首先看c1+c2-k (l1+l2-k) 这个式子 它得到的是该横(竖)方向最多可以摆的战舰数
搭嘎 当前点在该行(列)的位置也关乎投放系数 这时候前面保存的4个数值就起作用了
想象战舰从一端向另一端逐格移动 要想使当前点在战舰中 只有min(c1(l1),c2(l2))个位置满足
结合之前的限制条件 一点的投放系数就是 c1+c2-k, c1, c2 三者最小值
即ans[x][y]=min(min(c1,c2),c1+c2-k)+min(min(l1,l2),l1+l2-k)
重点已解决,按深搜模板打暴力即可
代码C++
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
char map[101][101];
bool vis[101][101];
int ans[101][101];
int res[2];
int dirx[4]={-1,0,1,0};
int diry[4]={0,1,0,-1};
int n,k;
void dfs(int x=1,int y=1)
{
vis[x][y]=true;
if(map[x][y]=='.')
{
int xx=x,yy=y;
int cnt_col1=0,cnt_line1=0;
int cnt_col2=0,cnt_line2=0;
while(map[xx--][yy]=='.')
{
cnt_col1++;
if(xx==0)
break;
}
xx=x;
while(map[xx++][yy]=='.')
{
cnt_col2++;
if(xx==n+1)
break;
}
xx=x;
while(map[xx][yy--]=='.')
{
cnt_line1++;
if(yy==0)
break;
}
yy=y;
while(map[xx][yy++]=='.')
{
cnt_line2++;
if(yy==n+1)
break;
}
if(cnt_col1+cnt_col2-1>=k)
ans[x][y]+=min(min(cnt_col2,cnt_col1),cnt_col1+cnt_col2-k);
if(cnt_line1+cnt_line2-1>=k)
ans[x][y]+=min(min(cnt_line1,cnt_line2),cnt_line1+cnt_line2-k);
}
for(int i=0;i<4;i++)
{
int xx=x+dirx[i];
int yy=y+diry[i];
if(xx>n||xx<1||yy>n||yy<1)
continue;
if(map[xx][yy]=='.'&&!vis[xx][yy])
dfs(xx,yy);
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<n+1;i++)
for(int j=1;j<n+1;j++)
cin>>map[i][j];
for(int i=1;i<n+1;i++)
for(int j=1;j<n+1;j++)
{
if(map[i][j]=='.'&&!vis[i][j])
dfs(i,j);
}
int maxn=-1;
for(int i=1;i<n+1;i++)
for(int j=1;j<n+1;j++)
if(ans[i][j]>maxn)
{
res[0]=i;
res[1]=j;
maxn=ans[i][j];
}
cout<<res[0]<<' '<<res[1];
return 0;
}