#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;

#define N 310

struct edge{
int x;
int y;
int t;
edge(int x, int y, int t): x(x), y(y), t(t){};
};

static char grid[N][N];
static bool st[N][N];
static int dx[4] = {0, -1, 0, 1};
static int dy[4] = {-1, 0, 1, 0};
static int d[3] = {2, 1, 0};
static int n, k;

int bfs(){
queue[HTML_REMOVED] q;
q.push(new edge(3, 3, 0));
st[3][3] = true;

while(!q.empty()){
    edge *e = q.front();
    q.pop();
    //原地不动情况入队
    q.push(new edge(e->x, e->y, e->t + 1));
    //遍历四个方向
    for(int i = 0; i < 4; i++){
        int a = e->x + dx[i], b = e->y + dy[i];
        int fat = (e->t / k) >= 2 ? 0 : d[e->t / k];
        if(st[a][b])
            continue;
        if(a - fat < 1 || a + fat > n || b - fat < 1 || b + fat > n)
            continue;
        bool flag = false;
        for(int u = a - fat; u <= a + fat; u++){
            for(int v = b - fat; v <= b + fat; v++){
                if(grid[u][v] == '*'){
                    flag = true;
                }
            }
        }
        if(flag)
            continue;
        if(a == n - 2 && b == n - 2)
            return e->t + 1;
        st[a][b] = true;
        q.push(new edge(a, b, e->t + 1));
    }
}
return -1;

}

int main(){
cin >> n >> k;
for(int i = 1; i <= n; i){
for(int j = 1; j <= n; j){
char c;
scanf(“%c”, &c);
grid[i][j] = c;
printf(“%c”, grid[i][j]);
}
}
printf(“%d”, bfs());
return 0;
}

为什么我跟你写的一模一样 只是换成用C++写的 为什么题目给的案例运行结果是21 而不是16 我一个个字母对着你的检查了一遍 看不出哪里不一样啊 折磨 呆佬可以帮我看看吗

你这每次都出队列一个，却又至少入队列一个（源点但时间+1了），如果到达不来终点，为什么不会死循环

最坏就是全部一遍，发现没到终点，st保证不走重复路

我想问的是，如果没有终点，while里面的return永远不会执行，每次队列的大小至少唯一，不会死循环吗

如果题目没有解，就死循环了，这题题目保证有解，所以不会死循环

是不是因为无论他走还是不走，时间都是变化的

如果一直是走动的的为什么一开始要加1呢????
q.add(new Edge(t.x, t.y, t.time + 1));

//将源点加入到队列
q.add(new Edge(t.x, t.y, t.time + 1));
这个地方可以有一个优化，如果时间让体积已经减到最小了，那么原地停留没有意义了。时间优化了三倍

为什么一定要根据当前的体型去判断呢 走到下一位置不应该是去按照下一位置的体型去判断吗

从当前位置走到下一个位置是有一个过程的，整个过程都需要满足不被障碍物卡住才能走过去，可以理解成在走到下一个位置时，体积慢慢减少，而不是瞬间减少，因此只能用当前的体积去走下一个位置

啊 懂了 感谢大佬

if (flag）
{
q.add(new Edge(tEdge.x, tEdge.y, tEdge.time + 1));
continue;
}

将原点加入队列换成这样写为什么不对

完整代码

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

import javax.xml.namespace.QName;

public class Main {
    static int N = 310;
    static char[][] g = new char [N][N];
    static boolean[][] st = new boolean[N][N];
    static int dx[] = {0, -1, 0, 1};
    static int dy[] = {-1, 0, 1, 0};
    static int step[] = {2, 1, 0}; // 5, 3, 1
    static int k, n;
    public static void main(String args[])
    {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        k = s.nextInt();
        for (int i = 1; i <= n; i++)
        {
            char[] temp = s.next().toCharArray();
            for (int j = 1; j <= n; j++)
                g[i][j] = temp[j - 1];
        }
        System.out.println(bfs());
    }
    static int bfs()
    {
        Queue<Edge> q = new LinkedList<>();
        q.add(new Edge(3, 3, 0));
        st[3][3] = true;
        while (!q.isEmpty())
        {
            Edge tEdge = q.poll();
            q.add(new Edge(tEdge.x, tEdge.y, tEdge.time + 1));

            for (int i = 0; i < 4; i++)
            {
                int a = tEdge.x + dx[i], b = tEdge.y + dy[i];
                int fat = tEdge.time / k >= 2 ? 0 : step[tEdge.time/k];
                if (a + fat > n || a - fat < 1 || b + fat > n || b - fat < 1) continue;
                if (st[a][b]) continue;
                boolean flag = false;
                for (int u = a - fat; u <= a + fat; u++)
                    for (int v = b - fat; v <= b + fat; v++)
                        if (g[u][v] == '*')
                            flag = true;
                if (flag)
                {
                    q.add(new Edge(tEdge.x, tEdge.y, tEdge.time + 1));
                    continue;
                }
                if (a == n - 2 && b == n - 2) return tEdge.time  +1;
                st[a][b] = true;
                q.add(new Edge(a, b, tEdge.time + 1));
            }
        }
        return -1;
    }
}
class Edge
{
    int x, y, time;
    public Edge(int x, int y, int time)
    {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}

因为在枚举原点时，在for (int i = 0; i < 4; i++)这段前面你已经把在源点不动的状态，加入到队列中，后面枚举4个方向时，若存在障碍物，又把源点不动的状态加入到队列中，会导致存在重复遍历的点，其实这一步是没必要的。因此数据范围较大时就会超时

q.add(new Edge(t.x, t.y, t.time + 1)); 大佬 为什么这行代码 写成 dx[4]=0 dy[4]=0; 是不对的呢

如果给dx, dy多加一个0, 0的偏移量, 这一句代码是一定不会被执行的, 因为会被st[a][b]continue掉原点

对

哇 知道了 感谢

nb

大佬，复杂度是怎么计算的

每个位置最多只走一次，最多走$n^2$个位置，最多在某个位置停留$2k$次，因此时间复杂度是$O(n^2 + 2k)$

修改下，停留的次数最多是$2k$

我跟你基本一样 但是我用BufferedReader输入流超时了 用Scanner居然不超时 啥情况？

代码

Queue[HTML_REMOVED]q=new LinkedList[HTML_REMOVED]();

    BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

    String str=reader.readLine();

    String []arr=str.split(" ");

    col=row=Integer.parseInt(arr[0]);

    k=Integer.parseInt(arr[1]);

    //采用BufferedReader输入流

    /*Scanner input=new Scanner(System.in);

    row=col=input.nextInt();
    k=input.nextInt();*/

    graph=new char[row][col];

    stab=new boolean[row][col];

    for(int i=0;i<row;i++) {

        graph[i]=reader.readLine().toCharArray();

        //graph[i]=input.next().toCharArray();
    }

好吧 现在Buffered提交居然可以过了 可能评测系统原因？

完整代码.....理论上来说是不会超时的

在代码里面加三个`，把代码框出来

不知道

大佬，您代码里只有上下左右四种情况，没有体现原地不动消耗脂肪的情况呀？

将原点加入到队列 注释的 下一行就是了

tql,呆佬