洛谷p1141 01迷宫题解

刚才在洛谷做了一道bfs的题目，不想让昨天dhz大佬讲的bfs白讲了

如图这就是dhz大佬的真面目哈哈哈哈

洛谷p1141 01迷宫题解

但是刚开始自己一边看着题解一边自己打了一下，发现超时了三个点，怎么优化，关同步都不顶用，下面贴一下我的超时代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char mp[2000][2000];
bool bk[2000][2000];
int step[2000][2000];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int ans;
int sx,sy;
struct node {
  int x;
  int y;
};
int bk1,bk2;
void bfs(int x,int y) {
  queue<node>q;
  node a;
  a.x=x;
  a.y=y;
  q.push(a);
  while(!q.empty()) {
    node b;
    b=q.front();
    q.pop();
    for(int i=0;i<4;i++) {
      node c;
      c.x=b.x+dx[i];
      c.y=b.y+dy[i];
      bk1=mp[b.x][b.y];
      bk2=mp[c.x][c.y];
      if(bk1!=bk2&&c.x>0&&c.y>0&&c.x<=n&&c.y<=n&&!bk[c.x][c.y]) {
        ans++;
        step[c.x][c.y]=step[b.x][b.y]+1;
        bk[c.x][c.y]=1;
        q.push(c);
      }
    }
  }
}
int main() {
  cin>>n>>m;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) {
      cin>>mp[i][j];
    }
    while(m--)  {
      cin>>sx>>sy;
      ans=1;
      memset(step,0,sizeof(step));
      memset(bk,0,sizeof(bk));
      bk[sx][sy]=1;
      bfs(sx,sy);
      cout<<ans<<endl;
    }
}

后来实在没办法了，洛谷题解又都看不懂，就去看了一下dhz的博客，发现他的优化方式很独特啊：先把每种情况的答案全部存起来，dx和dy来对应每一个t，输入每一个sx和sy都有存好的答案放到了a数组中，这个思路真是tql 但是我刚开始打了一次发现还是错了原因是我把用来辅助存答案和判断走没走过的数组bk设成了一个bool数组，到头来只存了一个答案，也因为这个题巧了，两个样例答案还都一样一直没有发现哪里的问题

洛谷p1141 01迷宫题解

这图见证了了我的艰难的心路历程

#include<bits/stdc++.h>//bool数组的代码 wawawawa
using namespace std;
char mp[2000][2000];
bool  bk[2000][2000];
int a[200000];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int sum;
int t=1;
int sx,sy;
struct node {
  int x;
  int y;
}b;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin>>mp[i][j];
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(!bk[i][j]) {
        queue<node>q;
        b.x=i;
        b.y=j;
        q.push(b);
        sum++;
        bk[i][j]=t;
        while(!q.empty()) {
          b=q.front();
          q.pop();
          for(int k=0;k<4;k++) {
            node d=b;
            d.x=b.x+dx[k];
            d.y=b.y+dy[k];
            if(!bk[d.x][d.y]&&d.x<n&&d.x>=0&&d.y>=0&&d.y<n&&(mp[d.x][d.y]!=mp[b.x][b.y])) {
              bk[d.x][d.y]=t;
              sum++;
              q.push(d);
            }
          }
        }
        a[t]=sum;
        sum=0;
        t++;
      }
      while(m--) {
        cin>>sx>>sy;
        cout<<a[bk[sx-1][sy-1]]<<endl;
      }
}

最后附上ac代码：

#include<bits/stdc++.h>
using namespace std;
char mp[2000][2000];
int  bk[2000][2000];
int a[200000];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int sum;
int t=1;
int sx,sy;
struct node {
  int x;
  int y;
}b;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin>>mp[i][j];
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(!bk[i][j]) {
        queue<node>q;
        b.x=i;
        b.y=j;
        q.push(b);
        sum++;
        bk[i][j]=t;
        while(!q.empty()) {
          b=q.front();
          q.pop();
          for(int k=0;k<4;k++) {
            node d=b;
            d.x=b.x+dx[k];
            d.y=b.y+dy[k];
            if(!bk[d.x][d.y]&&d.x<n&&d.x>=0&&d.y>=0&&d.y<n&&(mp[d.x][d.y]!=mp[b.x][b.y])) {
              bk[d.x][d.y]=t;
              sum++;
              q.push(d);
            }
          }
        }
        a[t]=sum;
        sum=0;
        t++;
      }
      while(m--) {
        cin>>sx>>sy;
        cout<<a[bk[sx-1][sy-1]]<<endl;
      }
}

洛谷p1141 01迷宫题解

相关推荐