问题描述
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入格式
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5
样例说明
其合根情况参考下图
代码：
java：
import java.util.Scanner;
public class Main {
// public List<int[]> list = new ArrayList<int[]>();
public int[][] list;
public int[] juzhen;
public int index = 0;
public int find(){
int count = 0;
while(index < juzhen.length){
for(int i = 0;i<juzhen.length;i++){
if(juzhen[i] == 0){
set(i);
break;
}
}
count++;
}
System.out.println(count);
return 0;
}
public void set(int index_x){
if(juzhen[index_x] == 0){
juzhen[index_x] = 1;
index++;
for(int i = 0;i<list[index_x].length;i++){
if(list[index_x][i] != -1 ){
set(list[index_x][i]);
}
}
}
return ;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int m = input.nextInt(); int n = input.nextInt();
int[] juzhen = new int[m*n];
Main main = new Main();
int k = input.nextInt();
main.list = new int[m*n][4];
for(int i = 0;i<m*n;i++){
int[] list = {-1,-1,-1,-1};
juzhen[i] = 0;
main.list[i] = list;
}
for(int i = 0;i<k;i++){
int index = input.nextInt();
int page = input.nextInt();
if(page == index-n){
main.list[index-1][0] = page-1;
main.list[page-1][2] = index-1;
}else if(page == index+1){
main.list[index-1][1] = page-1;
main.list[page-1][3] = index-1;
}else if(page == index+n){
main.list[index-1][2] = page-1;
main.list[page-1][0] = index-1;
}else {
main.list[index-1][3] = page-1;
main.list[page-1][1] = index-1;
}
}
main.juzhen = juzhen;
main.find();
}
}
c++:
#include<stdio.h>
typedef struct node{
int num; //当前植物的编号
struct node *Up; //当前植物上面链接的植物
struct node *Down; //当前植物下面链接的植物
struct node *Left; //当前植物左面链接的植物
struct node *Right; //当前植物右面链接的植物
}Node;
void init( Node *, int );
void input( Node *, int , int );
void insert( Node *, int, int, int );
void search( Node *, int, int *, int );
void change( Node *, int * );
int main(void){
int m, n, k, point=0;
scanf("%d%d%d", &m, &n, &k );
Node tree[m*n]; //创建拥有m*n个合根植物的tree结构体数组
init( tree, m*n ); //初始化tree结构体数组
input( tree, k , n ); //输入合根植物连根的情况
search( tree, m*n, &point, 0 ); //开始搜索合根植物数
printf("%d\n", point );
return 0;
}
void change( Node *root, int *ch ){
ch[root->num - 1] = 1; //更新检测数组
if( root->Up != NULL && ch[root->Up->num - 1] == 0 ){ //分别向四个方向搜索是否有连根情况
change( root->Up, ch );
}
if( root->Down != NULL && ch[root->Down->num - 1] == 0 ){
change( root->Down, ch );
}
if( root->Left != NULL && ch[root->Left->num - 1] == 0 ){
change( root->Left, ch );
}
if( root->Right != NULL && ch[root->Right->num - 1] == 0 ){
change( root->Right, ch );
}
}
void search( Node *root, int n, int *pp, int k ){
static int check[1000 * 1000] = {0}; //检测数组 记录已经搜索过的连根
if( k == n ){ //搜索出口
return ;
}
if( check[k] == 0 ){
change( &root[k], check ); //一个新的合根植物入口，搜索到底
++ *pp; //合根植物数量更新
}
search( root, n, pp, k+1 );
}
void insert( Node *root, int head, int tail , int n ){
if( head == tail - 1 ){
root[head - 1].Right = &root[tail - 1];
root[tail - 1].Left = &root[head - 1];
}
if( head == tail + 1 ){
root[head - 1].Left = &root[tail - 1];
root[tail - 1].Right = &root[head - 1];
}
if( head == tail - n ){
root[head - 1].Down = &root[tail - 1];
root[tail - 1].Up = &root[head - 1];
}
if( head == tail + n ){
root[head - 1].Up = &root[tail - 1];
root[tail - 1].Down = &root[head - 1];
}
}
void input( Node *root, int k, int n ){
int head, tail, i;
for( i = 0 ; i < k ; i ++ ){
scanf("%d%d", &head, &tail );
insert( root, head, tail, n ); //更新连根情况
}
}
void init( Node *root, int n ){
int i ;
for( i = 0 ; i < n ; i ++ ){
root[i].num = i+1;
root[i].Up = NULL;
root[i].Down= NULL;
root[i].Left= NULL;
root[i].Right=NULL;
}
}