不是谁告诉我这为啥超时?=]]]]

//不就是一个种子填充算法吗
#include<bits/stdc++.h>
using namespace std;
int r,c;
char a[250][250];
struct st
{
    int xx,yy;
    st(int xx1,int yy1){xx=xx1;yy=yy1;}
};
queue<st>q; 
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>a[i][j];
    int ansk=0,ansv=0;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            if(a[i][j]!='#')
            {
                int ck=0,cv=0;
                q.push(st(i,j));
                if(a[i][j]=='k')ck++;
                if(a[i][j]=='v')cv++;
                a[i][j]='#';
                while(!q.empty())
                {
                    int x=q.front().xx,y=q.front().yy;
                    for(int k=0;k<4;k++)
                    {
                        int nx=x+dir[k][0],ny=y+dir[k][1];
                        if(a[nx][ny]=='#'||nx<1||nx>r||ny<1||ny>c)continue;
                        if(a[nx][ny]=='k')ck++;
                        if(a[nx][ny]=='v')cv++;
                        a[nx][ny]='#';
                        q.push(st(nx,ny));
                    }
                    q.pop();
                }
                if(ck>cv)cv=0;
                else ck=0;
                ansk+=ck;ansv+=cv; 
            }
        }
    cout<<ansk<<' '<<ansv;
    return 0;
> }

2 条评论

  • 兄弟,宽搜不是这么打的

  • 不就是一个种子填充算法吗

    #include<bits/stdc++.h>
    using namespace std;
    char mp[255][255];
    int r,c,w,s;
    short dir[4][2]={0,1,1,0,0,-1,-1,0};
    struct jl
    {
        int x,y;
    };
    jl tool;
    void bfs(int i,int j)
    {
        int wa=0,sa=0;
        if(mp[i][j]=='k')sa++;
        if(mp[i][j]=='v')wa++;
        queue<jl>q;
        tool.x=i,tool.y=j;
        q.push(tool);
        mp[i][j]='#';
        while(!q.empty())
        {
            int x=q.front().x,y=q.front().y;
            for(int k=0;k<4;k++)
            {
                int nx=x+dir[k][0],ny=y+dir[k][1];
                if(mp[nx][ny]!='#'&&nx>1&&nx<r&&ny>1&&ny<c)
                {
                    if(mp[nx][ny]=='k')sa++;
                    if(mp[nx][ny]=='v')wa++;
                    mp[nx][ny]='#';
                    tool.x=nx,tool.y=ny;q.push(tool);
                }
            }
            q.pop();
        }
        if(sa>wa)s+=sa;
        else w+=wa;
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin>>r>>c;
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                cin>>mp[i][j];
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                if(mp[i][j]!='#')
                    bfs(i,j);
        cout<<s<<' '<<w<<endl;
        return 0;
    }
    
    

    23ms,超不了时

  • 1

信息

ID
2643
难度
7
分类
(无)
标签
递交数
30
已通过
7
通过率
23%
上传者