B Battleship
E Masha and two friends
B 传送门
题意：
战船上有占地n*n的房间cells[][]，只由当cells[i][j]=='.'时才能够容纳水手。
已知水手需要k个连续的房间'.'，可以是水平方向连续k个'.'或竖直方向的连续k个'.'。
问哪个坐标(x,y)含有最多的连续的k个房间，如果不存在，输出任意坐标。
题解：
我的做法：暴力
求出每个坐标最多含有多少种容纳水手的方式，找到最大的。
具体细节看代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=+; int n,k;
char cells[maxn][maxn]; int Find(int a,int b,int c)
{
int res=;
while(a <= c)
{
if(a+k- >= c && a+k- <= b)
res++;
a++;
}
return res;
}
int update(int curX,int curY)//查找(curX,curY)含有的解
{
int upX=curX,downX=curX;
while(upX- >= && cells[upX-][curY] == '.')
upX--;
while(downX+ <= n && cells[downX+][curY] == '.')
downX++; int leftY=curY,rightY=curY;
while(leftY- >= && cells[curX][leftY-] == '.')
leftY--;
while(rightY+ <= n && cells[curX][rightY+] == '.')
rightY++; int res=Find(upX,downX,curX);
res += Find(leftY,rightY,curY);
return res;
}
void Solve()
{
int res=;
int x=,y=;
for(int i=;i <= n;++i)
for(int j=;j <= n;++j)
{
if(cells[i][j] != '.')
continue;
int curRes=update(i,j);
if(res < curRes)
{
res=curRes;
x=i,y=j;
}
}
printf("%d %d\n",x,y);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i <= n;++i)
scanf("%s",cells[i]+);
Solve(); return ;
}
题目来源：CodeForces - 965B
E 传送门