BFS板子死活没找出错来

mot1ve @ 2020-04-07 15:07:20

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n;
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};
int dis[1010][1010],vis[1010][1010];
char f[1010][1010];
struct node{
    int a,b;
};
queue<node> q;
int x1,y1,fx,fy,sx,sy;
int bfs(int x,int y)
{
    q.push((node){x,y});
    vis[x][y]=1;
    while(!q.empty());
    {
        x1=q.front().a;
        y1=q.front().b;
        q.pop();
        if(x1==fx&&y1==fy)
        {
            return dis[x1][y1];
        }
        for(int i=0;i<4;i++)
        {
            int dx=x1+xx[i];
            int dy=y1+yy[i];
            if(dx>0&&dx<=n&&dy>0&&dy<=n&&vis[dx][dy]==0&&f[dx][dy]=='0')
            {
                vis[dx][dy]=1;
                dis[dx][dy]=dis[x1][y1]+1;
                q.push((node){dx,dy});
            }
        }
    }
}
char d;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>f[i][j];
        }
    }
    cin>>sx>>sy>>fx>>fy;
    cout<<bfs(sx,sy);
    return 0;
}

by xhQYm @ 2020-04-07 15:18:44

好玄学啊，我没看出来那里错了。qwq

by Tune_ @ 2020-04-07 15:24:52

@kuoluo03

这是我的AC代码：

#include<bits/stdc++.h>
using namespace std;
struct data
{
    int x,y,s;
}kk;
queue<data> q;
int n,sx,sy,fx,fy;
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
char a[1001][1001];
int bj[1001][1001]={0}; 
void bfs(int nx,int ny)
{
    kk.x=nx;kk.y=ny;kk.s=0;
    q.push(kk);
    while(!q.empty())
    {
        kk=q.front();
        q.pop();
//      cout<<kk.x<<" "<<kk.y<<" "<<kk.s<<endl;
        for(int i=1;i<=4;i++)
        {
            int xx=kk.x+dx[i],yy=kk.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&a[xx][yy]=='0'&&(bj[xx][yy]>kk.s+1||!bj[xx][yy]))
            {
                if(xx==fx&&yy==fy)
                {
                    cout<<kk.s+1;
                    return;
                }
                else
                {
                    data k;
                    k.x=xx;
                    k.y=yy;
                    k.s=kk.s+1;
                    bj[xx][yy]=kk.s+1;
                    q.push(k);
                }
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)cin>>a[i][j];
    cin>>sx>>sy>>fx>>fy;
    bfs(sx,sy);
    return 0;
}

希望能帮到你QWQ

by wpy233 @ 2020-04-07 15:25:56

@lucy2008 光给代码有啥用啊awa

by Enterprise_ @ 2020-04-07 15:33:16

@kuoluo03

这是我的AC代码：

#include<iostream>
using namespace std;
int n,fn,fm,ln,lm;
int head=0,tail=0;
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char a[1000][1000];
struct cc
{
  int i,j;
  int step;
}c[1000000];
bool b(int i,int j)
{
  if(i>-1&&i<n&&j>-1&&j<n&&a[i][j]=='0') return true;
  else return false;
}
int main()
{
  //init
  cin>>n;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin>>a[i][j];
  cin>>fn>>fm>>ln>>lm;
  //
  a[fn-1][fm-1]='1';
  c[head].i=fn-1;
  c[head].j=fm-1;
  c[head].step=0;
  if(fn==ln&&fm==lm)
  {
    cout<<c[head].step<<endl;
    return 0;
  }
  while(head<=tail)
  {
    for(int i=0;i<4;i++)
      if(b(c[head].i+way[i][0],c[head].j+way[i][1]))
      {
        tail++;
        c[tail].i=c[head].i+way[i][0];
        c[tail].j=c[head].j+way[i][1];
        c[tail].step=c[head].step+1;
        a[c[tail].i][c[tail].j]='1';
        //print
        if(c[tail].i==ln-1&&c[tail].j==lm-1)
        {
          cout<<c[tail].step<<endl;
          return 0;
        }
      }
    head++;
  }
  return 0;
} 

希望能帮到你QWQ

by mot1ve @ 2020-04-07 15:34:06

大哥们别发代码啊 代码题解都有 我想知道我这个哪里错了 谢谢了！

by Ckger @ 2020-04-07 15:34:25

@kuoluo03 你距离存的方式错了吧，不能保证最优解

by mot1ve @ 2020-04-07 15:36:09

@森蚺 问题是这个连输出都没有

by Ckger @ 2020-04-07 15:37:23

@kuoluo03 也是这个原因

by Ckger @ 2020-04-07 15:37:59

@kuoluo03 你的代码意思就是一个点只能走一次

by mot1ve @ 2020-04-07 15:39:21

@森蚺 这是bfs啊大哥，而且肯定只走一次啊