题目描述

 * l自己写一遍 整体的思想就是这个胖子每次都是在自己所占区域的中心位置了，其实题目已经说的很明白了
 * 当这个胖子是5*5的时候，胖子处于中心位置，就像题目中说的，胖子是5*5的时候起点在3*3，
 * 终点是n-2*n-2,表示5*5就是一个整体，只不过为了简便计算，以中心位置为点进行计算
 * 所以当这个胖子移动的时候还需要考虑这一步在移动的过程中判断是否存在障碍物 另外还需要注意的时候需要加上时间，是三维的

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class PII {
    int x;
    int y;
    int time;

    public PII(int x, int y, int time) {
        super();
        this.x = x;
        this.y = y;
        this.time = time;
    }

}

public class Main  {



    static int N = 310, n, k;
    static boolean st[][] = new boolean[N][N];
    static char [][]g = new char [N][N];
    static int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
    static int fat[] = { 2, 1, 0 };
    static Queue<PII> queue = new LinkedList<PII>();

    public static void bfs() {


        while (!queue.isEmpty()) {
            PII tPii = queue.poll();
            int x = tPii.x;
            int y = tPii.y;
            int time = tPii.time;
        if (x == n - 2 && y == n - 2) {
                System.out.println(time);
                return;
            }
            // 不动
            queue.add(new PII(x, y, time + 1));

            for (int i = 0; i < 4; i++) {
                int a = x + dx[i];
                int b = y + dy[i];
                int r = time / k;
                if (r > 2)
                    r = 0;
                else {
                    r=fat[r];
                }
                if (a + r > n || b + r > n || a - r <= 0 || b - r <= 0)
                    continue;
                if (st[a][b])
                    continue;
                boolean flag = false;
                for (int j = a - r; j <= a + r; j++) {
                    for (int z = b - r; z <= b + r; z++) {
                        if (g[j][z] == '*') {
                            flag = true;
                            break;
                        }
                        if (flag)
                            break;
                    }
                }
                if (flag)
                    continue;

                st[a][b]=true;
                queue.add(new PII(a, b, time+1));

            }

        }

    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String p[]=bufferedReader.readLine().split(" ");

        //Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(p[0]);
        k=Integer.parseInt(p[1]);

        for (int i = 1; i <= n; i++) {
            String pp=bufferedReader.readLine();
            for(int j=1;j<=n;j++) {
                g[i][j]=pp.charAt(j-1);
            }
        }
            queue.add(new PII(3, 3, 0));
            st[3][3]=true;
            //一定要记得置为true
        bfs();
    }

}