洛谷 P1443 马的遍历

P1443 马的遍历

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 

3 3 1 1

输出样例#1： 

0    3    2

3    -1   1

2    1    4    
思路：搜索。

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m,tx,ty;

int ans[][],vis[][];

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

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

struct nond{

    int x,y,pos;

};

int main(){

    scanf("%d%d%d%d",&n,&m,&tx,&ty);

    nond tmp;vis[tx][ty]=;

    tmp.x=tx;tmp.y=ty;tmp.pos=;

    queue<nond>que;

    que.push(tmp);

    while(!que.empty()){

        nond now=que.front();

        que.pop();

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

            nond c;

            c.x=dx[i]+now.x;

            c.y=dy[i]+now.y;

            c.pos=now.pos+;

            if(c.x>=&&c.x<=n&&c.y>=&&c.y<=m&&!vis[c.x][c.y]){

                ans[c.x][c.y]=c.pos;vis[c.x][c.y]=;

                que.push(c);

            }

        }

    }

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

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

            if(!vis[i][j])    ans[i][j]=-;

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

        }

        cout<<endl;

    }

}