程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

藍橋杯官網 試題 PREV-111 歷屆真題 大胖子走迷宮【第十屆】【決賽】【研究生組】【C++】【Java】【Python】

編輯:Python

 為幫助大家能在6月18日的比賽中有一個更好的成績,我會將藍橋杯官網上的歷屆決賽題目的四類語言題解都發出來。希望能對大家的成績有所幫助。


今年的最大目標就是能為【一億技術人】創造更高的價值。


資源限制

內存限制:256.0MB   C/C++時間限制:1.0s   Java時間限制:3.0s   Python時間限制:5.0s

​編輯​編輯

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}; // 右、左、下、上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;}

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])



  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved