首页 > 试题广场 >

对称飞行器

[编程题]对称飞行器

热度指数：3514 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小强在玩一个走迷宫的游戏，他操控的人物现在位于迷宫的起点，他的目标是尽快的到达终点。
每一次他可以选择花费一个时间单位向上或向下或向左或向右走一格，或是使用自己的对称飞行器花费一个时间单位瞬移到关于当前自己点中心对称的格子，且每一次移动的目的地不能存在障碍物。
具体来说，设当前迷宫有 $\mathit n$ 行 $\mathit m$ 列，如果当前小强操控的人物位于点 $\mathit A(x,y)$ ，那么关于点 $\mathit A$ 中心对称的格子 $\mathit B(x',y')$ 满足 $\mathit x+x'=n+1$ 且 $\mathit y+y'=m+1$ 。
需要注意的是，对称飞行器最多使用 $\text 5$ 次。

输入描述:

第一行两个空格分隔的正整数  ，分别代表迷宫的行数和列数。
接下来  行 每行一个长度为  的字符串来描述这个迷宫。
其中
 代表通路。
 代表障碍。
 代表起点。
 代表终点。
保证只有一个  和 一个  。

输出描述:

仅一行一个整数表示从起点最小花费多少时间单位到达终点。
如果无法到达终点，输出  。

示例1

输入

4 4
#S..
E#..
#...
....

输出

说明

一种可行的路径是用对称飞行器到达  再向上走一步，再向右走一步，然后使用一次对称飞行器到达终点。

算法知识视频讲解

Java

sczhu

参考大佬写了个Java版

import java.util.*;

public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[][][] dp;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] tmp = line.split(" ");
        int m = Integer.parseInt(tmp[0]);
        int n = Integer.parseInt(tmp[1]);
        char[][] map = new char[m][n];
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for (int i = 0; i < m; i++) {
            line = scanner.nextLine();
            for (int j = 0; j < n; j++) {
                char ch = line.charAt(j);
                map[i][j] = ch;
                if (ch == 'S') {
                    sx = i;
                    sy = j;
                }
                if (ch == 'E') {
                    ex = i;
                    ey = j;
                }
            }
        }
        
        bfs(map, sx, sy, ex, ey);
        for (int i = 0; i < 6; i++) {
            if (dp[ex][ey][i] != 0) {
                System.out.println(dp[ex][ey][i]);
                return;
            }
        }
        System.out.println(-1);
    }
    
    public static void bfs(char[][] map, int sx, int sy, int ex, int ey) {
        Deque<int[]> queue = new ArrayDeque<>();
        int m = map.length;
        int n = map[0].length;
        dp = new int[m][n][6];
        
        queue.offerFirst(new int[] {sx, sy, 0});
        while (!queue.isEmpty()) {
            int[] status = queue.pollLast();
            int x = status[0], y = status[1], t = status[2];
            int nx = 0, ny = 0, nt = 0;
            for (int i = 0; i < 5; i++) {
                if (i == 4) {
                    nx = m - 1 - x;
                    ny = n - 1 - y;
                    nt = t + 1;
                } else {
                    nx = x + dx[i];
                    ny = y + dy[i];
                    nt = t;
                }
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && nt < 6 && map[nx][ny] != '#' && dp[nx][ny][nt] == 0) {
                    dp[nx][ny][nt] = dp[x][y][t] + 1;
                    if (nx == ex && ny == ey) {
                        return;
                    }
                    queue.offerFirst(new int[] {nx, ny, nt});
                }
            }
        }
    }
}

发表于 2021-07-19 22:53:03 回复(1)