A40797. 估计人数
填空题
困难
知识点
题目描述
估计人数
题目描述
给定一个 N × M 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。
已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。
走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。
请你计算至少有多少人在矩阵上走过。
输入格式
输入第一行包含两个整数 N、M。
以下 N 行每行包含 M 个整数 (0/1)，代表方格矩阵。
输出格式
输出一个整数代表答案。
测试样例1
Input：
5 5
00100
11111
00100
11111
00100
Output：
3
1
2
3
4
5
6
7
8
9
10
评测用例规模与约定
对于所有评测用例，1 ≤ N, M ≤ 20，标记为 1 的方格不超过 200 个。
参考答案
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;
}
}
}
上一题
下一题