1496065964
第八届蓝桥杯决赛 之 合根植物
问题描述：大概题意 在 n 行 m 列的矩阵里，格子编号为 1 - n * m（1 <= n,m <= 100），接下来是 k 行的两个数a b（分别表示两个格子之间可以合根），需要计算有多少种生长方法
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
例如输入
5 4 15
1 5
2 3
3 7
7 11
11 12
4 8
5 9
9 10
9 13
13 17
17 18
18 19
10 14
14 15
15 19
结果输出 6
解题思路
题目一览而过，相信有底气的人都能直接给套上bfs，没错就是他，而且数据量不是很大，可行！
一个map标记两个格子互通，一个全局的vis数组进行标记，然后就是广度进行上下左右搜索，卧槽，决赛题目竟然这么简单啊，我。。。
代码实现
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
合根植物
@author Ape
/
public class J6 {static final int MAX = 101;
static int N, M, ans = 0;
static int[] r;
static int[][] map = new int[MAX][MAX];
static int[] vis = new int[MAX];static void bfs(int n){
if(vis[n] == 1) return; Queue<Integer> queue = new LinkedList<Integer>(); queue.add(n); vis[n] = 1; while(!queue.isEmpty()){ int now = queue.poll(); for(int i = 0; i < 4; i++){ int next = now + r[i]; if(next > 0 && next <= N * M && vis[next] == 0 && map[now][next] == 1){ vis[next] = 1; queue.add(next); } } } ans++;}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); N = scanner.nextInt(); M = scanner.nextInt(); r = new int[]{ 1, -1, M, -M }; int n = scanner.nextInt(); for(int i = 0; i < n; i++){ int a = scanner.nextInt(); int b = scanner.nextInt(); map[a][b] = 1; map[b][a] = 1; } for(int i = 1; i <= N * M; i++) bfs(i); System.out.println(ans); scanner.close();}
}