最少步数&P1443 马的遍历

1330：【例8.3】最少步数

s数组：记录（1,1）到达每一点需要的最少步数

s[1][1]自然为 0，其余初始化为 -1

que数组：que[#][1] 表示（1,1）可到达点的 x 坐标

que[#][2] 表示（1,1）可到达点的 y 坐标

que[#][3] 表示（1,1）可到达点的 最少步数

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

using namespace std;

int dx[]={-,-,-,,,,,,,-,-,-},

    dy[]={-,-,-,-,-,-,,,,,,};

int main()

{

    int s[][],que[][]={},x1,y1,x2,y2;

    memset(s,0xff,sizeof(s));   //s数组初始化

    int head=,tail=;          //初始位置入队

    que[][]=;que[][]=;que[][]=;

    cin>>x1>>y1>>x2>>y2;

    while(head<=tail)

    {

        for(int d=;d<=;d++)   //拓展十二个方向

        {

            int x=que[head][]+dx[d];

            int y=que[head][]+dy[d];

            if(x>&&y>)     //保证不出界

              if(s[x][y]==-)   //未走过

              {

                  s[x][y]=que[head][]+;

                  tail++;

                  que[tail][]=x;

                  que[tail][]=y;

                  que[tail][]=s[x][y];

                  if(s[x1][y1]>&&s[x2][y2]>)

                  {

                    cout<<s[x1][y1]<<endl;

                    cout<<s[x2][y2]<<endl;

                   return ;

                }

              }

        }

        head++;

    }

}

以上我方代码已修改

没修改前：

（如果你发现）

原因是：

（去掉“pause”之后就。。就。。可以了)

P1443 马的遍历

题解

BFS队列实现，和上面那个题本质是一样的

注意判断行走的是有效区域！！！

代码

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstdlib>

using namespace std;

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''&&ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n,m,sx,sy;

int pan[][];

struct node

{

    int x,y,step;

};

queue<node> q;

int dx[]={-,-,-,-,,,,};

int dy[]={-,,-,,-,,-,};

int main()

{

    n=read();m=read();sx=read();sy=read();

    memset(pan,-,sizeof(pan));

    pan[sx][sy]=;

    q.push((node){sx,sy,});

    while(!q.empty())

    {

        node now=q.front();

        q.pop();

        for(int i=;i<;i++)

        {

            int xx=now.x +dx[i];

            int yy=now.y +dy[i];

            if(pan[xx][yy]==-&&xx>=&&xx<=n&&yy>=&&yy<=m)

            {

                pan[xx][yy]=now.step +;

                q.push((node){xx,yy,pan[xx][yy]}) ;

            }

        }

    }

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

          printf("%-5d",pan[i][j]);

        printf("\n");

    }

    return ;

}

（但是之前我试过注释掉它 ybt 瓦特掉了所以显示一个点运行错误。。）

ybt就是欺负我这个lao shi ren