洛谷 P1331 海战

传送门

题解：由于船是方形的，所以比较简单。但是考试的时候跪了，orz。忘了考虑类似一圈井号中间有一摊水。

         可以只考虑这个点上方和左边点的情况，这样分为四种情况。一种是左边是一滩水，上面是船，那么这个点与上面的点构成船。另一种正好相反。第三种是左边和上面都是水，那么它自己先构成船。第四种是左边和上面都是船，但是不是同一条船。这时船相邻。那么这样子考虑的话，一定会有不满足方形的船出现。因此在搜到一滩水的时候，判断它的上方和左边有没有船，如果都有船，且不是同一条，则有船相邻。

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 1100

using namespace std;

char a[N][N];

int f[N][N]={};

int r,c,sum=;

int main()

{

    scanf("%d%d",&r,&c);

    for (int i=;i<=r;i++)

      for (int j=;j<=c;j++)

        cin>>a[i][j];

    for (int i=;i<=r;i++)

      for (int j=;j<=c;j++)

         {

             if (a[i][j]=='.') f[i][j]=;

             if (a[i][j]=='#')

               {

                  int x=f[i-][j],y=f[i][j-];

                     if (x!=&&y!=&&x!=y)

                     {

                           cout<<"Bad placement."<<endl;

                            return ;

                     }

                   else if (x==&&y!=) f[i][j]=y;

                   else if (x!=&&y==) f[i][j]=x;

                   else if (x==&&y==) f[i][j]=++sum;

               }

         }

    printf("There are %d ships.\n",sum);

    return ;

}

蠢蛋的60分代码

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 1100

using namespace std;

char a[N][N];

int f[N][N]={};

int r,c,sum=;

int main()

{

    scanf("%d%d",&r,&c);

    for (int i=;i<=r;i++)

      for (int j=;j<=c;j++)

        cin>>a[i][j];

    for (int i=;i<=r;i++)

      for (int j=;j<=c;j++)

         {

            int x=f[i-][j],y=f[i][j-];

             if (a[i][j]=='.')

               {

                     if (x==y&&x!=)

                       {

                            cout<<"Bad placement."<<endl;

                            return ;

                       }

                     f[i][j]=;

               }

             if (a[i][j]=='#')

               {

                     if (x!=&&y!=&&x!=y)

                     {

                            cout<<"Bad placement."<<endl;

                            return ;

                     }

                   else if (x==&&y!=) f[i][j]=y;

                   else if (x!=&&y==) f[i][j]=x;

                   else if (x==&&y==) f[i][j]=++sum;

                   else if (x==y) f[i][j]=x;

               }

         }

    printf("There are %d ships.\n",sum);

    return ;

}

改后满分代码