玄关70分求条

P1141 01迷宫

lyc_qwq @ 2024-11-22 21:17:15

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0 , t = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            t = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * t;
}
inline void write(int x)
{
    if(x < 0)
    {
        putchar('-');
    }
    if(x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
const int N = 1010;
int n , m;
int o , oo;
int vis[N][N];
int sum;
int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {-1 , 0 , 1 , 0};
char a[N][N];
struct node
{
    int x;
    int y;
};

void bfs(int x , int y)
{
    queue <node> q;
    memset(vis , 0 , sizeof(vis));
    sum=0;
    q.push({x , y });
    vis[x][y]=1;
    sum=1;
    while(q.size())
    {
        node tmp = q.front();
        int tx = tmp.x;
        int ty = tmp.y;
        q.pop();
        for(int i = 0; i < 4; ++ i)
        {
            int ttx = tx + dx[i];
            int tty = ty + dy[i];
            if(ttx >= 1 && ttx <=n && tty >= 1 && tty <= n && a[ttx][tty] != a[tx][ty] && vis[ttx][tty] == 0)
            {
                q.push({ttx , tty });
                vis[ttx][tty] = 1;
                sum ++;
            }
        }
    }
}

int main()
{
    n = read() , m = read();
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = 1;j <= n; ++ j)
        {
            cin >> a[i][j];
        }
    }
    while(m --)
    {
        sum = 0;
        o = read() , oo = read();
        bfs(o , oo);
        write(sum);
        cout << '\n';
    }
    return 0;
}

请各位大佬帮本蒟蒻调一下代码

by chen_kun @ 2024-11-22 21:30:39

@lyc_qwq这道题是连通块问题，你每个数据都带进去重新算肯定会T。

正解是求出每个01连通块中每个点互相能走多少步，用数组存起来。查询的时候统一用

by lyc_qwq @ 2024-11-24 21:06:06

@chen_kun

额~~ 能直接改我的代码吗（我听不懂）

by chen_kun @ 2024-11-25 15:04:08

你自己看我的代码改一下吧

绝对不是因为我比较懒 

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,tx,ty,dx[5]={-1,1,0,0},dy[5]={0,0,-1,1},vis[1111][1111],ans,sum[1111],t=1,av[1111][1111];
char a[1111][1111];
struct node{
    int x,y;
};
void bfs(int x0,int y0){
    vis[x0][y0]=1;
    queue<node>q;
    q.push({x0,y0});
    ans=1;
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        q.pop();
        av[x][y]=t;
        for(int i=0;i<4;i++){
            tx=x+dx[i];
            ty=y+dy[i];
            if(a[x][y]!=a[tx][ty]&&vis[tx][ty]==0&&tx>=1&&tx<=n&&ty>=1&&ty<=n) vis[tx][ty]=1,q.push({tx,ty}),ans++;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){
                bfs(i,j);
                sum[t]=ans;
                t++;
            }
        }
    }
    while(m--){
        cin>>x>>y;
        cout<<sum[av[x][y]]<<endl;
    }
    return 0;
}
/*
2 2
01
10
1 1
2 2
*/

by lyc_qwq @ 2024-11-25 19:48:38

@chen_kun

好的（壶关）

|