最少步数&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[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},    
    dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
    
int main()
{
    int s[101][101],que[100001][4]={0},x1,y1,x2,y2;    
    memset(s,0xff,sizeof(s));   //s数组初始化 
    int head=1,tail=1;          //初始位置入队 
    que[1][1]=1;que[1][2]=1;que[1][3]=0;
    cin>>x1>>y1>>x2>>y2;
    while(head<=tail)
    {
        for(int d=0;d<=11;d++)   //拓展十二个方向 
        {
            int x=que[head][1]+dx[d];
            int y=que[head][2]+dy[d];
            if(x>0&&y>0)     //保证不出界 
              if(s[x][y]==-1)   //未走过 
              {
                  s[x][y]=que[head][3]+1;
                  tail++;
                  que[tail][1]=x;
                  que[tail][2]=y;
                  que[tail][3]=s[x][y];
                  if(s[x1][y1]>0&&s[x2][y2]>0)
                  {
                    cout<<s[x1][y1]<<endl;
                    cout<<s[x2][y2]<<endl;
                   return 0;    
                }
              }
        }
        
        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=0;
    char last=' ',ch=getchar();
    while(ch<'0'&&ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans;
}

int n,m,sx,sy;
int pan[405][405];
struct node 
{
    int x,y,step;
};
queue<node> q;
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};

int main()
{
    n=read();m=read();sx=read();sy=read();
    memset(pan,-1,sizeof(pan));
    pan[sx][sy]=0;
    q.push((node){sx,sy,0});
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int xx=now.x +dx[i];
            int yy=now.y +dy[i];
            if(pan[xx][yy]==-1&&xx>=1&&xx<=n&&yy>=1&&yy<=m)
            {
                pan[xx][yy]=now.step +1;
                q.push((node){xx,yy,pan[xx][yy]}) ;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
          printf("%-5d",pan[i][j]);
        printf("
");
    }
    return 0;
}

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

ybt就是欺负我这个lao shi ren