社区讨论

求助大佬

P114101迷宫参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi7xvsmm
此快照首次捕获于
2025/11/21 05:24
4 个月前
此快照最后确认于
2025/11/21 05:24
4 个月前
查看原帖
第一个TLE 70 分
C
#include<iostream>
#include<cstring>
#include<queue>
#include<math.h>
using namespace std;
#define N 1000+10
int n,m;
char map[N][N];
bool vis[N][N];
int fr[]={0,0,-1,1};
int ba[]={1,-1,0,0};
struct zb{
    int x,y;
};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>map[i][j];
	queue <zb> op;
    for(int i=1;i<=m;i++)
    {
        int ans=0;
        memset(vis,false,sizeof(vis));
        zb ll;
        cin>>ll.x>>ll.y;
        vis[ll.x][ll.y]=true;
        op.push(ll);
        while(!op.empty())
        {
            ans++;
            zb tmp=op.front();
            op.pop();
            for(int i=0;i<4;i++)
            {
                zb tmp1=tmp;
                tmp1.x+=fr[i];
                tmp1.y+=ba[i];
                if(tmp1.x&&tmp1.y&&tmp1.x<=n&&tmp1.y<=n&&map[tmp1.x][tmp1.y]!=map[tmp.x][tmp.y]&&!vis[tmp1.x][tmp1.y])
                    op.push(tmp1),vis[tmp1.x][tmp1.y]=true;
            }    
        }
        cout<<ans<<endl;
    }
}
第二个TLE 80 分
C
#include<iostream>
#include<cstring>
#include<queue>
#include<math.h>
using namespace std;
#define N 1000+10
int n,m,tot=0;
char map[N][N];
int hv[N][N];
int ans[N*N];
bool vis[N][N];
int fr[]={0,0,-1,1};
int ba[]={1,-1,0,0};
struct zb{
    int x,y;
};
int main()
{
                queue <zb> op;
    memset(hv,0,sizeof(hv));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>map[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(hv[i][j]==0)
            {
                tot++;
                hv[i][j]=tot;
                int sum=0;
                memset(vis,false,sizeof(vis));
                zb ll;
                ll.x=i;ll.y=j;
                vis[ll.x][ll.y]=true;
                op.push(ll);
                while(!op.empty())
                {
                    sum++;
                    zb tmp=op.front();
                    op.pop();
                    for(int i=0;i<4;i++)
                    {
                        zb tmp1=tmp;
                        tmp1.x+=fr[i];
                        tmp1.y+=ba[i];
                        if(tmp1.x&&tmp1.y&&tmp1.x<=n&&tmp1.y<=n&&map[tmp1.x][tmp1.y]!=map[tmp.x][tmp.y]&&!vis[tmp1.x][tmp1.y])
                        {
                            op.push(tmp1);
                            vis[tmp1.x][tmp1.y]=true;
                            hv[tmp1.x][tmp1.y]=tot;
                        }
                    }  
                }
                ans[tot]=sum;
            }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        cout<<ans[hv[a][b]]<<endl;
    }
}

回复

4 条回复,欢迎继续交流。

正在加载回复...