小猴编程周赛C++ | 六面世界

学习C++从娃娃抓起！记录下在学而思小猴编程学习过程中的题目，记录每一个瞬间。侵权即删，谢谢支持！

附上汇总贴：小猴编程C++ | 汇总-CSDN博客

【题目描述】

六面世界的地图由六边形格子组成，地图一共n行，奇数行有m格，偶数行有m-1格。下图是一个n=5，m=5的地图。

小明想从起点S走到终点E，但是地图上有敌国的骑士把守，每个骑士有自己的攻击距离k，它可以向6个方向直线攻击最多k个格子，小明不能进入会被骑士攻击到的格子。

给出起点S终点E和地图上的骑士位置和攻击距离，小明每次可以移动到1个相邻的格子。问小明从起点移动到终点最少需要多少次移动。

【输入】

第1行，两个正整数n，m

第2~n+1行，第2,4,…行每行有m格字符，第3,5,…行每行有m-1个字符且开头有一个空格。字符之间用空格隔开。

字符S表示起点，字符E表示终点，字符0表示空地，字符1~9表示一个骑士，他的攻击距离为这个数字。

【输出】

输入1个整数，小明的最少移动次数。如果无法到达终点，输出-1。

【输入样例】

5 5
1 0 0 0 0
 0 0 0 0
0 S 0 0 0 
 0 0 0 0 
0 2 0 0 E

【输出样例】

5

【代码详解】

#include <bits/stdc++.h>
using namespace std;
char a[1005][2005], vis[1005][2005];
int n, m, res=-1;
int dx[6] = {1, 1, -1, -1, 0, 0};
int dy[6] = {1, -1, 1, -1, 2, -2};
struct node {
    int x, y, step;
};

int main()
{
    cin >> n >> m;
    int stx, sty, edx, edy;  
    for (int i=1; i<=n; i++) {  // 初始化a数组和vis数组
        for (int j=1; j<2*m; j++) {
            a[i][j] = '0';  // 为方便排错，初始用'0'字符填充
            vis[i][j] = '0';
        }
    }
    for (int i=1; i<=n; i++) {  // 输入矩阵
        for (int j=i%2?1:2; j<2*m; j+=2) {
            cin >> a[i][j];
            if (a[i][j]=='S') stx=i, sty=j;  // 并记录起点
            if (a[i][j]=='E') edx=i, edy=j;  // 以及终点
        }
    }
    for (int x=1; x<=n; x++) {  // 预处理，将骑士周围的可以走的格子都标记为'1'
        for (int y=1; y<2*m; y++) {
            if (a[x][y]>='1' && a[x][y]<='9') {
                vis[x][y] = '1';
                int k = a[x][y] - '0';
                for (int i=1; i<=k; i++) {
                    for (int j=0; j<6; j++) {
                        int xx = x + i*dx[j];
                        int yy = y + i*dy[j];
                        if (xx>=1 && xx <=n && yy>=1 && yy<2*m) {
                            vis[xx][yy] = '1';
                        }
                    }
                }
            }
        }
    }
    queue<node> q;  // 定义队列
    node t = {stx, sty, 0};
    q.push(t);
    vis[stx][sty]='1';
    while (!q.empty()) {  // BFS搜索模板
        node tp = q.front();
        int x = tp.x, y=tp.y, step=tp.step;
        q.pop();
        if (tp.x == edx and tp.y == edy) {  // 当到达终点时，更新res为tp.step
            res = tp.step;
            break;
        }
        for (int i=0; i<6; i++) {  // 6个方向遍历
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx>=1 && xx<=n && yy>=1 && yy<2*m && vis[xx][yy]!='1') {  // 满足条件才可以走到下一个点
                vis[xx][yy] = '1';
                node t = {xx, yy , step+1};
                q.push(t);
            }
        }
    }
    cout << res << endl;  // 输出最短步数，如果BFS结束后还没有更新，则输出初始值-1
    return 0;
}

【运行结果】

5 5
1 0 0 0 0
 0 0 0 0
0 S 0 0 0
 0 0 0 0
0 2 0 0 E
5