暴力3tle,连通图7re求助谢谢大佬。。
  • 板块P1141 01迷宫
  • 楼主codeG0d
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/3/16 22:41
  • 上次更新2023/10/28 06:25:29
查看原帖
暴力3tle,连通图7re求助谢谢大佬。。
661318
codeG0d楼主2022/3/16 22:41
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool Map[1001][1001];
int later[4][2] = {0,1,0,-1,1,0,-1,0};
int ans[1001][1001];
struct node
{
    int x,y;
    node(int _x,int _y)
    {
        x = _x,y = _y;
    }
};
void bfs(int x,int y)
{
    deque<node> dq;
    if(ans[x][y])
        return;
    node tmp(x,y);
    dq.push_back(tmp);
    ans[x][y] = 1;
    for(deque<node>::iterator it = dq.begin();it != dq.end();it++)
    {   
        int _x = it->x,_y = it->y;
        int find = Map[_x][_y]?0:1;
        for(int i = 0;i < 4;i++)
        {
            int newx = _x + later[i][0],newy = _y + later[i][1];
            if(newx <= n && newx >= 1 && newy <= n && newy >= 1 && Map[newx][newy] == find && !ans[newx][newy])
            {
                node newnode(newx,newy);
                dq.push_back(newnode);
                ans[newx][newy] = 1;
            }
        }
    }
    int res = dq.size();
    for(auto i : dq)
    {
        int _x = i.x,_y = i.y;
        ans[_x][_y] = res;
    }
}
int main()
{
    char ch;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>ch;
            if(ch=='1') Map[i][j]=1;
            else Map[i][j]=0;
        }
    int p,q;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            bfs(i,j);
    for(int i = 0;i < m;i++)
    {
        cin >> p >> q;
        cout << ans[p][q] << endl;
    }
}

如题,我想请问为啥我联通图做法3ac7re,我ans数组是用来保存联通数目的。 我思路是默认ans为0表示没搜,然后针对每个未搜索点bfs,搜完了这个点关联的这一片联通图之后把这片联通图的每一个点的ans值全都更新为联通图面积,我认为这并不存在数组越界的隐患啊,求问大佬是什么原因,或者告知其中存在的re的隐患是啥,谢谢各位大佬 了。

2022/3/16 22:41
加载中...