题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入输出格式

输入格式：

 

一行四个数据，棋盘的大小和马的坐标

 

输出格式：

 

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

题解

//其中有好多重复标记的地方，请见谅#include
      
       using namespace std;queue 
       
         qx;//横坐标队列queue 
        
          qy;//纵坐标队列//我才不会告诉你是我懒得写结构体了呢int dx[9]={
    0,+2,+2,+1,+1,-1,-1,-2,-2};int dy[9]={
    0,+1,-1,+2,-2,+2,-2,+1,-1};//搜索时更改坐标int bx,by;//变换后的坐标int sx,sy;//起始坐标int nx,ny;//现在的坐标int n,m;//棋盘大小int ans[401][401];//答案数组bool bo[401][401];//判断是否走过 false表示不能走，反之能走void bfs(int x,int y);//BFSint main(){    cin>>n>>m;    memset(bo,false,sizeof(bo));//都不能走     可以一会在判断越界的时候少写几行...    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            ans[i][j]=-1;   //答案数组置为-1，若没有被更新则还是-1，可以直接输出    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            bo[i][j]=true;//输入的范围内能走    cin>>sx>>sy;    bfs(sx,sy);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            if(j==m) {printf("%-5d\n",ans[i][j]);}            else    {printf("%-5d",ans[i][j]);}//输出    return 0;}void bfs(int x,int y){    ans[x][y]=0;//起点步数为0    qx.push(x);//加入队列    qy.push(y);    while(!qx.empty()){      //队列非空        nx=qx.front();           //取出节点对其拓展        qx.pop();                   //删除节点        ny=qy.front();        qy.pop();        bo[nx][ny]=false;      //标记为不能走      for(int i=1;i<=8;i++){          bx=nx+dx[i];            //将要判断的节点          by=ny+dy[i];          if(bo[bx][by]==true){
    //判断可走              qx.push(bx);              qy.push(by);              bo[bx][by]=false;//不同起步可能指向相同节点 必须操作后马上就标记避免重复入队 不要担心重复标记 标了没事 不标大概率会T （我之前T了三次，还是看dalao题解才发现的...）              ans[bx][by]=ans[nx][ny]+1;          }        }    }}