为帮助大家能在6月18日的比赛中有一个更好的成绩,我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。
今年的最大目标就是能为【一亿技术人】创造更高的价值。
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
#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])