6 条题解

  • 0
    @ 2021-11-21 14:55:07

    #include<iostream>
    using namespace std;
    const int N=1001;
    int n,x1,y1,x2,y2;
    int a[N][N],xy[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    bool b[N][N];
    struct node
    {
    int x,y,div;
    }h[N*N];
    bool check(int x,int y)
    {
    if(x>0&&x<n+1&&y>0&&y<n+1)
    {
    return true;
    }
    return false;
    }
    void sb(int x,int y)
    {
    int head=0,tail=1;
    h[tail].x=x;
    h[tail].y=y;
    h[tail].div=0;
    b[x][y]=1;
    while(head<tail)
    {
    head++;
    int xx,yy;
    for(int i=0;i<4;i++)
    {
    xx=h[head].x+xy[i][0];
    yy=h[head].y+xy[i][1];
    if(b[xx][yy]==0&&check(xx,yy)&&a[xx][yy]==0)
    {
    b[xx][yy]=1;
    tail++;
    h[tail].x=xx;
    h[tail].y=yy;
    h[tail].div=h[head].div+1;
    if(xx==x2&&yy==y2)
    {
    cout<<h[tail].div;
    return ;
    }
    }
    }
    }
    }
    int main()
    {
    cin>>n;
    char c;
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=n;j++)
    {

    cin>>c;
    a[i][j]=c-'0';
    }
    }
    cin>>x1>>y1>>x2>>y2;
    sb(x1,y1);
    return 0;
    }

  • -1
    @ 2019-01-27 16:03:31

    举一反三:
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+10;
    char a[1010][1010];
    int n,sx,sy,ex,ey;
    int head,tail,hx[maxn],hy[maxn],step[maxn]={0};
    int nexx[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    void init()
    {
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cin>>sx>>sy>>ex>>ey;
    }
    bool check(int x,int y)
    {
    if(x<0||x>n-1||y<0||y>n-1) return false;
    return true;
    }
    void bfs(int txx,int tyy)
    {
    head=0,tail=1;
    hx[tail]=txx,hy[tail]=tyy,step[tail]=0;
    a[txx][tyy]='1';
    while(head<tail)
    {
    head++;
    for(int i=0;i<4;i++)
    {
    int tx,ty;
    tx=hx[head]+nexx[i][0];
    ty=hy[head]+nexx[i][1];
    if(check(tx,ty)&&a[tx][ty]=='0')
    {
    tail++;
    hx[tail]=tx;
    hy[tail]=ty;
    step[tail]=step[head]+1;
    a[tx][ty]='1';
    if((tx==ex-1)&&(ty==ey-1))
    {
    cout<<step[tail];
    }
    }
    }
    }
    }
    int main()
    {
    init();
    bfs(sx-1,sy-1);
    }

  • -1
    @ 2019-01-27 16:03:09

    答题解

  • -1
    @ 2019-01-27 16:02:57

    哈哈哈
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+10;
    int n,gx,gy,tx,ty;
    char a[1010][1010];
    int head,tail,step[maxn],hx[maxn],hy[maxn];
    int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    void init()
    {
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cin>>gx>>gy>>tx>>ty;
    }
    bool check(int x,int y)
    {
    if(a[x][y]=='1'||x<0||x>n||y<0||y>n) return 0;
    return 1;
    }
    void bfs(int x,int y)
    {
    head=0;
    tail=1;
    hx[tail]=x;
    hy[tail]=y;
    step[tail]=0;
    a[x][y]='1';
    while (head<tail)
    {
    head++;
    for(int i=0;i<4;i++)
    {
    int txx;
    int tyy;
    txx=hx[head]+f[i][0];
    tyy=hy[head]+f[i][1];
    if(check(txx,tyy))
    {
    tail++;
    hx[tail]=txx;
    hy[tail]=tyy;
    step[tail]=step[head]+1;
    a[txx][tyy]='1';
    if(txx==tx-1&&tyy==ty-1) cout<<step[tail];
    }
    }
    }
    }
    int main()
    {
    init();
    bfs(gx-1,gy-1);
    return 0;
    }

  • -1
    @ 2019-01-27 16:02:17

    正确答案:
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=3e6+10;
    int n,gx,gy,tx,ty;
    char a[1010][1010];
    int head,tail,step[maxn],hx[maxn],hy[maxn];
    int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    void init()
    {
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cin>>gx>>gy>>tx>>ty;
    }
    bool check(int x,int y)
    {
    if(a[x][y]=='1'||x<0||x>n||y<0||y>n) return 0;
    return 1;
    }
    void bfs(int x,int y)
    {
    head=0;
    tail=1;
    hx[tail]=x;
    hy[tail]=y;
    step[tail]=0;
    a[x][y]='1';
    while (head<tail)
    {
    head++;
    for(int i=0;i<4;i++)
    {
    int txx;
    int tyy;
    txx=hx[head]+f[i][0];
    tyy=hy[head]+f[i][1];
    if(check(txx,tyy))
    {
    tail++;
    hx[tail]=txx;
    hy[tail]=tyy;
    step[tail]=step[head]+1;
    a[txx][tyy]='1';
    if(txx==tx-1&&tyy==ty-1) cout<<step[tail];
    }
    }
    }
    }
    int main()
    {
    init();
    bfs(gx-1,gy-1);
    return 0;
    }

  • -1
    @ 2019-01-27 15:43:45

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e3+10;
    int n,gx,gy,tx,ty;
    char a[maxn][maxn];
    int head,tail,step[maxn],hx[maxn],hy[maxn];
    int f[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
    void init()
    {
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cin>>gx>>gy>>tx>>ty;
    }
    bool check(int x,int y)
    {
    if(a[x][y]=='0'&&x>=0&&x<n&&y>=0&&y<n) return 1;
    return 0;
    }
    void bfs(int x,int y)
    {
    head=0;
    tail=1;
    hx[tail]=x;
    hy[tail]=y;
    step[tail]=0;
    a[x][y]='1';
    while (head<tail)
    {
    head++;
    for(int i=0;i<4;i++)
    {
    int txx;
    int tyy;
    txx=hx[head]+f[i][0];
    tyy=hy[head]+f[i][1];
    if(check(txx,tyy))
    {
    tail++;
    hx[tail]=txx;
    hy[tail]=tyy;
    step[tail]=step[head]+1;
    a[txx][tyy]='1';
    if(txx==tx-1&&tyy==ty-1) cout<<step[tail];
    }
    }
    }
    }
    int main()
    {
    init();
    bfs(gx-1,gy-1);
    return 0;
    }

  • 1

信息

难度
7
分类
(无)
标签
递交数
229
已通过
46
通过率
20%
上传者