蓝桥杯官网 试题 PREV-111 历届真题 大胖子走迷宫【第十届】【决赛】【研究生组】【C++】【Java】【Python】三种解法

#include <bits/stdc++.h>
using namespace std;
const int N=310;
char s[N][N];
int n,k;
int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 右、左、下、上
bool vis[N][N];
struct node
{
	int x,y,cnt,len; // len表示大小，初始为2 
};
bool judge(int x,int y,int d,int len) 
// 方向d 假设到达(x,y) 判断可行性
{
	if(vis[x][y]||y+len>n||y-len<1||x+len>n||x-len<1)return 0;
	for(int i=x-len;i<=x+len;i++)
		for(int j=y-len;j<=y+len;j++)
			if(s[i][j]=='*')return 0;
	return 1;
}
int f(int cnt)
{
	int len;
	if(cnt<k)len=2; 
	else if(cnt<2*k)len=1;
	else len=0;
	return len;
}
int bfs()
{
	queue<node>q;
	q.push({3,3,0,2});
	vis[3][3]=1;
	while(!q.empty())
	{
		node tmp=q.front();
    q.pop();
		int x=tmp.x;
		int y=tmp.y;
		int cnt=tmp.cnt;
		int len=tmp.len;
		if(x==n-2&&y==n-2) return cnt;
		if(len!=0) // 现在还不是1*1，可能原地等待 
		{
			q.push({x,y,cnt+1,f(cnt+1)}); // 原地等待
		} 
		for(int i=0;i<4;i++)
		{
			int nx=x+dir[i][0];
			int ny=y+dir[i][1];
			if(judge(nx,ny,i,len)) // 判断新点(nx,ny)在原长度时能否移动 
			{
				vis[nx][ny]=1;
				q.push({nx,ny,cnt+1,f(cnt+1)});
			}
		}
	}
}
int main() 
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>s[i][j];
	int ans=bfs();
	printf("%d\n",ans);
	return 0;
}

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

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		sc.nextLine();
		
		for(int i=1; i<=n; i++)
		{
			char[] chs = sc.nextLine().toCharArray();
			for(int j=1; j<=n; j++) map[i][j] = chs[j-1]=='+';
		}
		sc.close();

		int r = answer();
		System.out.println(r);
	}
	public static int n, k;
	public static boolean[][] map = new boolean[302][302];
	public static boolean[][] route = new boolean[302][302];
	public static int answer()
	{
		int o = 2, t = 0;
		LinkedList<Coor> record = new LinkedList<Coor>();
		LinkedList<Coor> queue = new LinkedList<Coor>();
		Coor start = new Coor(3, 3, 0), end = new Coor(n-2, n-2, 0);
		queue.push(start);
		
		while(true)
		{
			if(t==k && o>0) {
				k *= 2; o--;
				for(Coor p : record)
				{
					if(p.t < t) p.t = t;
					queue.offer(p);
				}
				record.clear();
			}
			Coor p = queue.poll();
			if(p == null) {t++; continue;}
			
			if(t < p.t) t = p.t;
			
			//System.out.println(p.x+" "+p.y+" "+p.t);
			if(p.x==end.x && p.y==end.y) return p.t;
			
			boolean has = next(queue, p, o);
			if(has) record.add(p);
		}
	}
	public static boolean next(LinkedList<Coor> queue, Coor p, int o)
	{
		int x = p.x, y = p.y, t = p.t;
		boolean has = false;
		
		int i = x+1, j = y;
		if(!route[i][j]) {
			if(check(i, j, o)) {
				route[i][j] = true;
				queue.offer(new Coor(i, j, t+1));
			} else {has = true;}
		}
		i = x-1; j = y;
		if(!route[i][j]) {
			if(check(i, j, o)) {
				route[i][j] = true;
				queue.offer(new Coor(i, j, t+1));
			} else {has = true;}
		}
		i = x; j = y+1;
		if(!route[i][j]) {
			if(check(i, j, o)) {
				route[i][j] = true;
				queue.offer(new Coor(i, j, t+1));
			} else {has = true;}
		}
		i = x; j = y-1;
		if(!route[i][j]) {
			if(check(i, j, o)) {
				route[i][j] = true;
				queue.offer(new Coor(i, j, t+1));
			} else {has = true;}
		}
		return has;
	}
	public static boolean check(int x, int y, int o)
	{
		int xstart = x-o, xend = x+o, ystart = y-o, yend = y+o;
		if(xstart<1 || xend>n || ystart<1 || yend>n) return false;
		for(int i=xstart; i<=xend; i++) for(int j=ystart; j<=yend; j++)
		{
			if(map[i][j]) continue;
			return false;
		}
		return true;
	}
	public static void printMap()
	{
		for(int i=1; i<=n; i++)
		{
			for(int j=1; j<=n; j++) System.out.print(map[i][j]?' ':'+');
			System.out.println();
		}
	}
	
	public static class Coor
	{
		public int x, y, t;
		public Coor(int x, int y, int t) {
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
}

from queue import PriorityQueue

n, k = map(int, input().split())
m = []
for i in range(n):
    m.append((list(input())))

dir = [[0,1], [1,0], [0,-1], [-1,0]]
tl = [[True for _ in range(n)] for __ in range(n)]
tl[2][2] = 0

q = PriorityQueue()
q.put([0,2,2])

while not q.empty():
    p = q.get()
    x, y, t = p[1], p[2], p[0]

    if x == n-3 and y == n-3:
        print(t)
        break

    if t < k:
        l = 2
    elif k < t < 2*k:
        l = 1
    else:
        l = 0
    for i, j in dir:
        nx = x + i
        ny = y + j
        if -1+l < nx < n-l and -1+l < ny < n-l and tl[nx][ny]:
            flag1 = True
            for i in range(nx-l, nx+l+1):
                for j in range(ny-l, ny+l+1):
                    if m[i][j] == '*':
                        flag1 = False
                        break
                if not flag1:
                    break
            if flag1:
                q.put([t+1, nx, ny])
                tl[nx][ny] = False

    if t < k:
        q.put([k, x, y])
    elif t < 2 * k:
        q.put([2*k, x, y])