Test question prev-111 on the official website of the Blue Bridge Cup. Previous real questions: big fat people walk the maze [the 10th] [final] [Graduate group] [c++] [Java] [Python]

​

  To help you in 6 month 18 There was a better result in the competition on the th , I will post the four kinds of language solutions of the final questions on the official website of the Blue Bridge Cup . I hope it will be helpful to your achievements .

The biggest goal of this year is to 【 100 million technicians 】 Create higher value .

Resource constraints

Memory limit ：256.0MB   C/C++ The time limit ：1.0s   Java The time limit ：3.0s   Python The time limit ：5.0s

​ edit ​ edit

C++

#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}; // Right 、 Left 、 Next 、 On bool vis[N][N];struct node{ int x,y,cnt,len; // len Represent size , For the initial 2 };bool judge(int x,int y,int d,int len) // Direction d Suppose you arrive at (x,y) Judge the feasibility { 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) // Not yet 1*1, May be waiting in place { q.push({x,y,cnt+1,f(cnt+1)}); // Wait in place } 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)) // Judge new points (nx,ny) Whether it can move at the original length { 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;}

Java

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; } }}

Python

from queue import PriorityQueuen, 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] = 0q = 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])

​