专栏首页算法时空马走日(bfs)

马走日(bfs)

题目 江湖是什么,对于在象棋界厮杀的大钉来说, 江湖就是一个矩阵,他的目标,就是在江湖之中骑着马,从他的位置出发,走到终点。

当然,大钉的马也遵从中国象棋中的“马走日”的规则, 而且在矩阵中,也会有一些障碍物,马不能跳到障碍物上;如果大钉的马面前有障碍物,即被“别马腿”, 那么他将不能跳向有障碍物的左前和右前这两个方向。

请问最少需要多少步,大钉才能骑着马跳到终点。

输入格式:

有多组测试样例。

每组第一行输入两个数 n 和 m,代表矩阵的行数和列数,2≤n≤m<100。

接下来输入 n 行字符串,其中 ‘s’ 代表起点,’e’ 代表终点,’.’ 代表空地,’#’ 代表障碍物。

输出格式:

对应每组输入,输出骑马跳到终点的最小步数,如果跳不到终点,输出 -1。

样例输入

3 3
s..
...
..e

3 3
s#.
...
# .e

样例输出

4
-1
#include<iostream>
#include<queue>
#define Min 0xfffffff
using namespace std;

class Point{
    public: int x,y;
    public: int step;
};
char map[100][100];
int cx[8] = {2,2,1,1,-1,-1,-2,-2};//下 下 上 上 下 下 下 下 
int cy[8] = {1,-1,2,-2,2,-2,1,-1};//右 左 右 左 右 左 右 左 
int minn = Min;
int n,m;

//判定条件 
int check(int i,Point a,Point temp)
{
    //不能越界,不能撞墙 
    if(temp.x >= n||temp.x < 0||temp.y < 0||temp.y >=n||map[temp.x][temp.y] == '#')
    {
        return 0;
    }

    //不能 别马腿 
    switch(i)
    {
        case 0:
        case 1:return map[a.x+1][a.y] != '#';
        case 2:return map[a.x][a.y+1] != '#';
        case 3:return map[a.x][a.y-1] != '#';
        case 4:return map[a.x][a.y+1] != '#';
        case 5:return map[a.x][a.y-1] != '#';
        case 6:
        case 7:return map[a.x-1][a.y] != '#';
        default:return 0;
    }
    return 1;
}
void bfs()
{
    Point a,temp;
    queue<Point> q;
    a.x = 0;
    a.y =0;
    a.step = 0;
    map[0][0] = '#'; 
    q.push(a);
    while(!q.empty())
    {
        a = q.front();
        q.pop();
        for(int i = 0; i < 8; i++)//广度搜索 
        {
            temp.x = a.x + cx[i];
            temp.y = a.y + cy[i];
            temp.step = a.step+1;
            if(check(i,a,temp))
            {
                if(temp.x == n-1&&temp.y == m-1)
                {
                    if(temp.step < minn)
                    {
                        minn = temp.step;
                    }
                    continue;//防止顶点被设置为墙 
                }
                map[temp.x][temp.y] = '#';
                q.push(temp);//入对列 
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n ;i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
    bfs();
    cout << (minn==Min?-1:minn);
    return 0;   
}
感觉有某个地方错了,测试的时候错了,但是对于列子是对的,大家帮忙找找。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 欧拉计划 Problem10

    题目; 素数的和 所有小于10的素数的和是2 + 3 + 5 + 7 = 17。

    用户4492257
  • CODE:拯救伟哥

    题目 题目描述 Description 有一天,炜哥和欧能干一起去大魔王家里做(dao)客(luan),不巧被魔王发现了。魔王将炜哥和欧能干抓走了,关在...

    用户4492257
  • 迷宫问题(bfs)

    迷宫问题 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9112 ...

    用户4492257
  • SPOJ NWERC11B Bird tree

    题意:根据公式进行分析,当该数字小于1说明往左边走,当数字大于1说明往右边走 #include<stdio.h> int main() { int ...

    用户1624346
  • C++ 传递动态内存

    这部分内容在引用作为函数的参数这个blog中有一些涉及,为了讨论引用传递顺带了参数传递与指针传递,在这里从动态内存传递的角度梳理一下,先看这样一个题目: 下...

    chaibubble
  • 每日一题(8)

    解析: java在处理自增自减时,会使用临时变量存储,计算后再返回该值 自增自减原理一样,此处以自增为例

    KEN DO EVERTHING
  • Backtracking - 77. Combinations

    Given two integers n and k, return all possible combinations of k numbers out of...

    用户5705150
  • 嵌入式应用软件架构设计

    要做到嵌入式应用的代码逻辑清晰,且避免重复的造轮子,没有好的应用架构怎么行。 如果没有好的架构,移植将会是一件很痛苦的事情。

    特立独行的猫a
  • Educational Codeforces Round 59 (Rated for Div. 2) B. Digital root(思维)

    题目链接:http://codeforces.com/contest/1107/problem/B

    Ch_Zaqdt
  • getchar()和scanf()混合使用的坑

    最近在混合使用 getchar() 和 scanf() 的时候遇到一个坑,现在记录一下。

    nnngu

扫码关注云+社区

领取腾讯云代金券