2018.12.14 浪在ACM 集训队第九次测试赛

B　　Battleship　　

E　　Masha and two friends

题意：

    战船上有占地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 传送门

　　题解