@toc

1、题目描述

小明是个大胖子，或者说是个大大胖子，如果说正常人占用1×1 的面积，小明要占用 5×5 的面积。

由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。

小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。

朋友们设计了一个迷宫，迷宫可以看成是一个由 n×n个方阵组成的方阵，正常人每次占用方阵中1×1的区域，而小明要占用 5×5的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都有障碍物。

为了方便小明，朋友们把迷宫的起点设置在了第 3 行第 3 列，终点设置在 了第 n−2 行第 n−2 列。

小明在时刻 0 出发，每单位时间可以向当前位置的上、下、左、右移动单 位 1 的距离，也可以停留在原地不动。小明走迷宫走得很辛苦，如果他在迷宫里面待的时间很长，则由于消耗了很多脂肪，他会在时刻 k 变成一个胖子，只占用3×3 的区域。如果待的时间更长，他会在时刻 2k 变成一个正常人，只占用 1×1 的区域。注意，当小明变瘦时迷宫的起点和终点不变。

请问，小明最少多长时间能走到迷宫的终点。注意，小明走到终点时可能瘦了也可能没有变瘦。

输入描述

输入的第一行包含两个整数 n*,k （1≤n≤300，1≤k*≤1000）。

接下来 n 行，每行一个由 n个字符组成的字符串，字符为 + 表示为空地， 字符为 * 表示为阻碍物。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++

输出

16

运行限制

2、解题思路

乍一看，这题描述怎么这么长，仔细分析后发现其实就是一个非常经典的BFS/DFS搜素问题，不过这道题在平时的基础上加上了体积和花费的时间，且体积会随着时间的变化缩小。

刚开始小明的体积为 $5*5$，到k时刻会变成 $3*3$，到 $2k$时刻之后会变成 $1*1$，其实做法和我们平时的BFS差不多，但是我们每扩展一个点，都要判断走到这个点的时候是否合适：

• 目前的身躯是否碰到了墙壁
• 目前的身躯是否越界
• 当前的中心节点是否已经被访问过了

如果不越界，也没有碰到墙壁，且中心节点没有被访问过，那么标记当前节点的访问状态为true，然后加入队列。

这道题除了在上下左右四个方向搜索之外，还多了一个原地踏步操作，所以其实也可以理解成5个方向。

大概思路：先将初始点放入队列，然后只要队列非空我们就让队头节点出队，判断是否已经到达了终点，如果是，输出花费的时间。

如果不是终点，先将原地踏步这个节点入队列(注意：这里时间花费要+1),然后在上下左右四个方向进行搜索，每次搜索的时候我们计算一个fat值，就理解成身子的长度吧。

• 当 $t\ge2k,fat=0,也就是体积为1*1$
• 当 $2k\ge t>k,fat=1,也就是体积为3*3$
• 当 $t<k,fat=2，也就是体积为5*5$

假设我们扩展的节点为int tx = now.x + dir[0],int ty = now.y + dir[1],然后我们判断我们的体积是否越界、是否碰到墙壁、是否已经被访问过了，如果都没有那就标记 $(tx,ty)$的访问标志为true,然后将 $(tx,ty,now.t+1)$入队列继续搜索，直到找到终点那就输出最小花费的时间然后结束。

可能写代码的时候没有这么麻烦，这里解释的稍微有点啰嗦了。

3、代码实现(AC)

这里我第一次用Scanner的时候只通过了90%，换成BufferedReader就AC了，你可以再试试。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
//其实可以说是5个方向：上下左右+原地踏步
public class Main {
    public static int[][] dirs = {
            {-1, 0}, //上
            {1, 0},  //下
            {0, -1}, //左
            {0, 1}   //右
    };
    public static boolean[][] visited;//访问标记
    public static char[][] map; //存储地图
    public static int n;    //n*n大小
    public static int k;    //k

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        n=Integer.parseInt(arr[0]);
        k=Integer.parseInt(arr[1]);
        map = new char[n][n];
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            map[i]=br.readLine().toCharArray();
        }
        bfs();
    }

    public static void bfs() {
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(new Node(2, 2, 0));
        visited[2][2] = true;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if (now.x == n - 3 && now.y == n - 3) {
                System.out.println(now.t);
                return;
            }
            //原地踏步+上下左右五个方向探索
            queue.offer(new Node(now.x, now.y, now.t + 1));
            for (int[] dir : dirs) {
                int tx = now.x + dir[0];
                int ty = now.y + dir[1];
                //根据时刻决定身形大小：>=2k:fat=0(1*1)，>=k:fat=1(3*3), <k:fat=2(5*5)
                int fat = (now.t >= 2 * k ? 0 : (now.t >= k ? 1 : 2));
                if (tx - fat < 0 || ty - fat < 0 || tx + fat >= n || ty + fat >= n) {   //加上肥胖的身躯是否越界
                    continue;
                }
                if (map[tx][ty] == '*' || visited[tx][ty]) {//中心点是否是墙壁||已经被访问过
                    continue;
                }
                if(check(tx,ty,fat)){ //判断(tx,ty)则条路是否可以走：判断身子有没有碰到墙壁
                    visited[tx][ty] = true;
                    queue.offer(new Node(tx, ty, now.t + 1));
                }
            }
        }
    }

    //检测身子有没有碰到墙壁
    public static boolean check(int x, int y,int fat) {
        for (int i = x - fat; i <= x + fat; i++) {
            for (int j = y - fat; j <= y + fat; j++) {
                if(map[i][j]=='*'){
                    return false;
                }
            }
        }
        return true;
    }

}

class Node {
    int x;
    int y;
    int t;

    public Node() {
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "x=" + x +
                ", y=" + y +
                ", t=" + t +
                '}';
    }
}

跑一个用例看看：

是否可以AC: