/ Vijos / 讨论 / 海战 /

TLE(6)(8)两个点,求解???

#include<iostream>
using namespace std;
int r,c,xj,sj,zj,yj,zs=0,ans=0,ship=0;
char tu[1500][1500];
int dfs(int x,int y)
{
    if(x<sj)
    sj=x;
    if(x>xj)
    xj=x;
    if(y<zj)
    zj=y;
    if(y>yj)
    yj=y;
    if(tu[x][y+1]=='#')
    dfs(x,y+1);
    if(tu[x+1][y]=='#')
    dfs(x+1,y);
}
void cover(int p,int q)
{
    tu[p][q]='.';
    if(tu[p][q-1]=='#')
    cover(p,q-1);
    if(tu[p][q+1]=='#')
    cover(p,q+1);
    if(tu[p+1][q]=='#')
    cover(p+1,q);
}
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;++i)
    {
        for(int j=1;j<=c;++j)
        {
            cin>>tu[i][j];
            if(tu[i][j]=='#')
            ans++;
        }
    }
    for(int i=1;i<=r;++i)
    {
        for(int j=1;j<=c;++j)
        {
            if(tu[i][j]=='#')
            {
                xj=-1,sj=1500,zj=1500,yj=-1;
                dfs(i,j);
                zs=zs+((yj-zj+1)*(xj-sj+1));
                ship++;
                cover(i,j);
            }
        }
    }
if(zs==ans)
cout<<"There are "<<ship<<" ships.";
else
cout<<"Bad placement.";
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1076
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
3107
已通过
1032
通过率
33%
被复制
10
上传者