Java 大学B组第十届蓝桥杯 2019年国赛真题( 六 ) _小明

<= 32 || c == 127) c = getByte();return c;}int nextInt() {int n = 0, c = split();boolean flag = true;if (c == '-') {c = getByte();flag = false;}while (c >= '0' && c <= '9') {n = n * 10 + (c & 0xf);c = getByte();}return flag? n: -n;}}}
广搜单源最短路
题目不难，优化麻烦
这里地图数字的意思是在 map[i][j] * k 的时间可以达到此地
其实可以把边界也看做是障碍物，这样用 O(n) 的空间就可以换取每一步减少 4个越界判断，但想到的时候已经快写完了，就算了，不会对其性质造成影响
#I 估计人数
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
给定一个 N × M 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。
已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。
走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1 ，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。
请你计算至少有多少人在矩阵上走过。
输入格式
输入第一行包含两个整数 N、M 。
以下 N 行每行包含 M 个整数 (0/1) ，代表方格矩阵。
输出格式
输出一个整数代表答案。
测试样例1
Input：5 50010011111001001111100100Output：3
评测用例规模与约定
对于所有评测用例， 1 ≤ N, M ≤ 20 ，标记为 1 的方格不超过 200 个。
code：
import java.io.IOException;import java.io.InputStream;import java.util.Arrays;public class Main {static int V = 1;static int source[];static boolean graph[][], marked[];public static void main(String[] args) {InputReader in = new InputReader(System.in);int n = in.nextInt(), m = in.nextInt();int idx[][] = new int[n + 1][m + 1];for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (in.split() == '1')idx[i][j] = V++;graph = new boolean[V][V];marked = new boolean[V];source = new int[V];for (int i = 0, v; i < n; i++)for (int j = 0; j < m; j++)if (idx[i][j] > 0) {v = idx[i][j];if (idx[i + 1][j] > 0)graph[v][idx[i + 1][j]] = true;if (idx[i][j + 1] > 0)graph[v][idx[i][j + 1]] = true;}for (int k = 1; k < V; k++)for (int i = 1; i < V; i++)for (int j = 1; j < V; j++)graph[i][j] |= graph[i][k] & graph[k][j];int cnt = 0;for (int i = 1; i < V; i++) {Arrays.fill(marked, false);cnt += dfs(i)? 1: 0;}System.out.print(V - cnt - 1);}static boolean dfs(int v) {for (int i = 1; i < V; i++) {if (graph[v][i]) {if (marked[i]) continue;marked[i] = true;if (source[i] == 0 || dfs(source[i])) {source[i] = v;return true;}}}return false;}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 <= 32 || c == 127) c = getByte();return c;}int nextInt() {int n = 0, c = split();boolean flag = true;if (c == '-') {c = getByte();flag = false;}while (c >= '0' && c <= '9') {n = n * 10 + (c & 0xf);c = getByte();}return flag? n: -n;}}}
匈牙利算法，难点在于构图，影响中蓝桥练习系统里面有道简单题练的就是这种构图，懒得去找了
#J 分考场
时间限制: 10.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
古语有云：春风得意马蹄疾，一日看尽长安花。
当然在一场考试中所有人都春风得意马蹄疾是不可能的，尤其是碰到一些毒瘤出题人的时候。

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

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