菊厂笔试3

马走日

输入一个矩阵，H为开始，T为结束，#为已经放置的棋子，问最少走多少步到达终点

输入样例 H->T
5 13
. . . . . . . . H . . . #
. . . . . . . . # . . . .
. . . . . # . . . . . . .
. # . . . . . . . . . . .
. . . . . . . . . . T # .

输出:
4

5 13
. . . . . H . . . . . . #
. . . . . . . . # . . . .
. . . . . # . . . . . . .
. # . . . . . . . . . . .
. . . . . . . . . . T # .

输出:
3

使用广度优先遍历判别8个方向，走时判断有没有卡马脚问题，和下一步是不是落在已有棋子的位置上。

package com.cgq.thread;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 测试样例 H->T
5 13
. . . . . . . . H . . . #
. . . . . . . . # . . . .
. . . . . # . . . . . . .
. # . . . . . . . . . . .
. . . . . . . . . . T # .

 输出:
 4

5 13
. . . . . H . . . . . . #
. . . . . . . . # . . . .
. . . . . # . . . . . . .
. # . . . . . . . . . . .
. . . . . . . . . . T # .

 输出:
 3
 **/

class Node{
    //坐标类
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class huawei3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String[] num = scanner.nextLine().split(" ");
            int row = Integer.parseInt(num[0]);
            int col = Integer.parseInt(num[1]);
            int startx = 0;
            int starty = 0;
            int endx = 0;
            int endy = 0;
            int[][] dp = new int[row][col];
            boolean[][] visited = new boolean[row][col];
            for (int i = 0; i < row; i++) {
                String[] input = scanner.nextLine().split(" ");
                for (int j = 0; j < col; j++) {
                    if(input[j].equals(".")){
                        dp[i][j] = Integer.MAX_VALUE;
                    }
                    else if (input[j].equals("#")){
                        dp[i][j] = -1;
                    }
                    else if(input[j].equals("H")){
                        dp[i][j] = 0;
                        startx = i;
                        starty = j;
                    }
                    else {
                        dp[i][j] = Integer.MAX_VALUE;
                        endx = i;
                        endy = j;
                    }
                }
            }
            bfs(startx, starty, endx, endy, dp, visited);
        }
    }

    public static void bfs(int startx, int starty, int endx, int endy, int[][] dp, boolean[][] visited){
        Node node = new Node(startx, starty);
        visited[startx][starty] = true;
        int row = visited.length;
        int col = visited[0].length;
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            Node frontNode = queue.poll();
            //方向1 x：-1，y: -2
            if(frontNode.x - 1 >= 0 && frontNode.y - 2 >= 0 && !visited[frontNode.x - 1][frontNode.y - 2]){
                if(dp[frontNode.x][frontNode.y - 1] != -1 && dp[frontNode.x - 1][frontNode.y - 2] != -1){
                    visited[frontNode.x - 1][frontNode.y - 2] = true;
                    queue.add(new Node(frontNode.x - 1, frontNode.y - 2));
                    dp[frontNode.x - 1][frontNode.y - 2] = Math.min(dp[frontNode.x - 1][frontNode.y - 2], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向2 x：-2，y: -1
            if(frontNode.x - 2 >= 0 && frontNode.y - 1 >= 0 && !visited[frontNode.x - 2][frontNode.y - 1]){
                if(dp[frontNode.x - 1][frontNode.y] != -1 && dp[frontNode.x - 2][frontNode.y - 1] != -1){
                    visited[frontNode.x - 2][frontNode.y - 1] = true;
                    queue.add(new Node(frontNode.x - 2, frontNode.y - 1));
                    dp[frontNode.x - 2][frontNode.y - 1] = Math.min(dp[frontNode.x - 2][frontNode.y - 1], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向3 x：-2，y: 1
            if(frontNode.x - 2 >= 0 && frontNode.y + 1 < col && !visited[frontNode.x - 2][frontNode.y + 1]){
                if(dp[frontNode.x - 1][frontNode.y] != -1 && dp[frontNode.x - 2][frontNode.y + 1] != -1){
                    visited[frontNode.x - 2][frontNode.y + 1] = true;
                    queue.add(new Node(frontNode.x - 2, frontNode.y + 1));
                    dp[frontNode.x - 2][frontNode.y + 1] = Math.min(dp[frontNode.x - 2][frontNode.y + 1], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向4 x：-1，y: 2
            if(frontNode.x - 1 >= 0 && frontNode.y + 2 < col && !visited[frontNode.x - 1][frontNode.y + 2]){
                if(dp[frontNode.x][frontNode.y + 1] != -1 && dp[frontNode.x - 1][frontNode.y + 2] != -1){
                    visited[frontNode.x - 1][frontNode.y + 2] = true;
                    queue.add(new Node(frontNode.x - 1, frontNode.y + 2));
                    dp[frontNode.x - 1][frontNode.y + 2] = Math.min(dp[frontNode.x - 1][frontNode.y + 2], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向5 x：1，y: 2
            if(frontNode.x + 1 < row && frontNode.y + 2 < col && !visited[frontNode.x + 1][frontNode.y + 2]){
                if(dp[frontNode.x][frontNode.y + 1] != -1 && dp[frontNode.x + 1][frontNode.y + 2] != -1){
                    visited[frontNode.x + 1][frontNode.y + 2] = true;
                    queue.add(new Node(frontNode.x + 1, frontNode.y + 2));
                    dp[frontNode.x + 1][frontNode.y + 2] = Math.min(dp[frontNode.x + 1][frontNode.y + 2], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向6 x：2，y: 1
            if(frontNode.x + 2 < row && frontNode.y + 1 < col && !visited[frontNode.x + 2][frontNode.y + 1]){
                if(dp[frontNode.x + 1][frontNode.y] != -1 && dp[frontNode.x + 2][frontNode.y + 1] != -1){
                    visited[frontNode.x + 2][frontNode.y + 1] = true;
                    queue.add(new Node(frontNode.x + 2, frontNode.y + 1));
                    dp[frontNode.x + 2][frontNode.y + 1] = Math.min(dp[frontNode.x + 2][frontNode.y + 1], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向7 x：2，y: -1
            if(frontNode.x + 2 < row && frontNode.y - 1 >= 0 && !visited[frontNode.x + 2][frontNode.y - 1]){
                if(dp[frontNode.x + 1][frontNode.y] != -1 && dp[frontNode.x + 2][frontNode.y - 1] != -1){
                    visited[frontNode.x + 2][frontNode.y - 1] = true;
                    queue.add(new Node(frontNode.x + 2, frontNode.y - 1));
                    dp[frontNode.x + 2][frontNode.y - 1] = Math.min(dp[frontNode.x + 2][frontNode.y - 1], dp[frontNode.x][frontNode.y] + 1);
                }
            }
            //方向8 x：1，y: -2
            if(frontNode.x + 1 < row && frontNode.y - 2 >= 0 && !visited[frontNode.x + 1][frontNode.y - 2]){
                if(dp[frontNode.x][frontNode.y - 1] != -1 && dp[frontNode.x + 1][frontNode.y - 2] != -1){
                    visited[frontNode.x + 1][frontNode.y - 2] = true;
                    queue.add(new Node(frontNode.x + 1, frontNode.y - 2));
                    dp[frontNode.x + 1][frontNode.y - 2] = Math.min(dp[frontNode.x + 1][frontNode.y - 2], dp[frontNode.x][frontNode.y] + 1);
                }
            }
        }
        if(dp[endx][endy] == Integer.MAX_VALUE){
            System.out.println(-1);
        }
        else {
            System.out.println(dp[endx][endy]);
        }
    }
}