90分求助两个点re

P1141 01迷宫

elpsconr @ 2024-04-02 23:30:03

求助两个点re,我感觉是结构体开的数组大小不够,但是我不知道怎么在不改变写法的前提下扩大数组空间

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e3+5;
int n,m;
char a[N][N];
int st[N][N];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1},f[N*100][2];
queue<PII> q;
void bfs(int x,int y)
{
  int res=1;
  f[res][0]=x,f[res][1]=y;
  st[x][y]=1;
  q.push({x,y});
  while(!q.empty())
  {
    int w=q.front().first,e=q.front().second;q.pop();
    for(int i=0;i<4;++i)
    {
        int xx=w+dx[i],yy=e+dy[i];
        if(xx<0||yy<0||xx>n-1||yy>n-1||st[xx][yy]||(a[xx][yy]==a[w][e])) continue;
        st[xx][yy]=1;q.push({xx,yy});res++;f[res][0]=xx,f[res][1]=yy;
    }
  }
  for(int i=1;i<=res;++i) 
  {
    st[f[i][0]][f[i][1]]=res;
  } 
}
int main()
{
  cin>>n>>m;
  for(int i=0;i<n;++i)
  {
    for(int j=0;j<n;++j)
    cin>>a[i][j];
  }
  while(m--)
  {
    int u,v;cin>>u>>v;
    u--,v--;
    if(!st[u][v]) bfs(u,v);
    cout<<st[u][v]<<endl;
  }
  return 0;
}

by elpsconr @ 2024-04-02 23:34:26

发现问题了,但是还是有疑问,不是10的五次方吗,为啥开1e6的数组


by I_like_play_eggy @ 2024-04-18 19:12:34

@elpsconr 我一开始也是因为这个,开 O_2 WA,不开 RE,后来发现的。因为有 n^2 个格子,n\le10^3,如果极端数据所有点互不连通,那么就要开 10^6


|