甘肃龙网

  1. 首页 > 生活 > >

Java 大学B组 第十届蓝桥杯 2019年国赛真题( 五 )

生活百科小明


为了方便小明 ， 朋友们把迷宫的起点设置在了第 3 行第 3 列 ， 终点设置在了第 n-2 行第 n-2 列 。
小明在时刻 0 出发 ， 每单位时间可以向当前位置的上、下、左、右移动单位 1 的距离 ， 也可以停留在原地不动 。小明走迷宫走得很辛苦 ， 如果他在迷宫里面待的时间很长 ， 则由于消耗了很多脂肪 ， 他会在时刻 k 变成一个胖子 ， 只占用 3 × 3 的区域 。如果待的时间更长 ， 他会在时刻 2k 变成一个正常人 ， 只占用 1 × 1 的区域 。注意 ， 当小明变瘦时迷宫的起点和终点不变 。
请问 ， 小明最少多长时间能走到迷宫的终点 。注意 ， 小明走到终点时可能变瘦了也可能没有变瘦 。
输入格式
输入的第一行包含两个整数 n, k 。
接下来 n 行 ， 每行一个由 n 个字符组成的字符串 ， 字符为 + 表示为空地 ， 
字符为 * 表示为阻碍物 。
输出格式

Java 大学B组 第十届蓝桥杯 2019年国赛真题

文章插图
输出一个整数 ， 表示答案 。
测试样例1
Input：9 5+++++++++++++++++++++++++++++++++++++++++++++***+*****+++++++++++++++++++++++++++Output：16
评测用例规模与约定
对于 30% 的评测用例 ， 1 ≤ n ≤ 50 。
对于 60% 的评测用例 ， 1 ≤ n ≤ 100 。
对于所有评测用例 ， 1 ≤ n ≤ 300 ， 1 ≤ k ≤ 1000 。
code：
import java.io.IOException;import java.io.InputStream;import java.util.LinkedList;import java.util.Queue;public class Test {public static void main(String[] args) {InputReader in = new InputReader(System.in);int n = in.nextInt(), k = in.nextInt();if (n <= 5) System.out.print('0');else {int map[][] = new int[n][n], INF = 0x3F3F3F3F;boolean[][] visit = new boolean[n][n];for (int i = 0, hi = n - 1; i <= hi; i++) {if (i < hi)map[1][i] = map[hi - 1][i] = map[i][1] = map[i][hi - 1] = 1;map[0][i] = map[hi][i] = map[i][0] = map[i][hi] = 2;}int[] os2i = { -1, -1, 0, 1, 1, 1, 0, -1 };int[] os2j = { 0, 1, 1, 1, 0, -1, -1, -1 };int[] os1i = { -2, -2, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2 };int[] os1j = { 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1 };for (int i = 0, x, y; i < n; i++)for (int j = 0; j < n; j++) {if (in.split() == '*') {map[i][j] = INF;for (int l = 0; l < 8; l++) {x = i + os2i[l];y = j + os2j[l];if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] > 2) continue;map[x][y] = 2;}for (int l = 0; l < 16; l++) {x = i + os1i[l];y = j + os1j[l];if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] > 1) continue;map[x][y] = 1;}}}class Step {int x, y, time;Step (int x, int y, int time) {this.x = x;this.y = y;this.time = time;}Step relax() {this.time++;return this;}}Queue> queue = new LinkedList();int[] offsetX = { -1, 0, 1, 0 };int[] offsetY = { 0, 1, 0, -1 };int endX = n - 3, endY = n - 3;queue.offer(new Step(2, 2, 0));while (queue.size() > 0) {Step now = queue.poll();if (now.x == endX && now.y == endY) {System.out.print(now.time);break;}for (int i = 0, x, y, s; i < 4; i++) {x = now.x + offsetX[i];y = now.y + offsetY[i];s = now.time / k;if (x < 0 || x >= n || y < 0 || y >= n || visit[x][y] || map[x][y] > s) continue;visit[x][y] = true;queue.offer(new Step(x, y, now.time + 1));}queue.offer(now.relax());}}}static class InputReader {InputStream in;int next, len;byte[] buff;InputReader(InputStream in) { this(in, 8192); }InputReader(InputStream in, int buffSize) {this.buff = new byte[buffSize];this.next = this.len = 0;this.in = in;}int getByte() {if (next >= len)try {next = 0;len = in.read(buff);if (len == -1) return -1;} catch (IOException e) {e.fillInStackTrace();}return buff[next++];}int split() {int c = getByte();while (c


上一篇：解决eclipse创建maven工程之后

下一篇：水分散粒剂是液体么？