蓝桥杯算法特训第七课【图】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第七课【图】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 连通性

给定一个方阵,定义连通:上下左右相邻,并且值相同。
可以想象成一张地图,不同的区域被涂以不同颜色。
输入:
整数N, (N<50)表示矩阵的行列数
接下来N行,每行N个字符,代表方阵中的元素
接下来一个整数M,(M<1000)表示询问数
接下来M行,每行代表一个询问,
格式为4个整数,y1,x1,y2,x2,
表示(第y1行,第x1列) 与 (第y2行,第x2列) 是否连通。
连通输出true,否则false

例如:
10
0010000000
0011100000
0000111110
0001100010
1111010010
0000010010
0000010011
0111111000
0000010000
0000000000
3
0 0 9 9
0 2 6 8
4 4 4 6

程序应该输出:
false
true
true

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
public class A
{
  static boolean lian_tong(char[][] data, int y1, int x1, int y2, int x2){
    if(y1==y2 && x1==x2) return true;
    char old = data[y1][x1];
    data[y1][x1]='*';
    try{
      if(y1>0 && data[y1-1][x1]==old && lian_tong(data,y1-1,x1,y2,x2)) return true;
      if(y1<data.length-1 && data[y1+1][x1]==old && lian_tong(data,y1+1,x1,y2,x2)) return true; if(x1>0 && data[y1][x1-1]==old && lian_tong(data,y1,x1-1,y2,x2)) return true;
      if(x1<data.length-1 && data[y1][x1+1]==old && lian_tong(data,y1,x1+1,y2,x2)) return true;
    }
    finally{
      data[y1][x1] = old;
    }
    return false;
  }
 
  public static void main(String[] args){
    Scanner  scan = new Scanner(System.in);
   
    int n = Integer.parseInt(scan.nextLine());
    char[][] data = new char[n][];
    for(int i=0; i<n; i++){
      data[i] = scan.nextLine().toCharArray();
    }
   
    int m = Integer.parseInt(scan.nextLine());
    for(int i=0; i<m; i++){
      String[] ss = scan.nextLine().split(" ");
      int y1 = Integer.parseInt(ss[0]);
      int x1 = Integer.parseInt(ss[1]);
      int y2 = Integer.parseInt(ss[2]);
      int x2 = Integer.parseInt(ss[3]);
     
      System.out.println(lian_tong(data,y1,x1,y2,x2));
    }
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int lian_tong(char* data[],int len, int y1, int x1, int y2, int x2)
{
    if (y1 == y2 && x1 == x2)
      return 1;
    char old = data[y1][x1];
    data[y1][x1] = '*';
    if (y1 > 0 && data[y1 - 1][x1] == old && lian_tong(data, len, y1 - 1, x1, y2, x2))
    {
      data[y1][x1] = old;
      return 1;
    }
     
    if (y1<len - 1 && data[y1 + 1][x1] == old && lian_tong(data, len,y1 + 1, x1, y2, x2)) { data[y1][x1] = old; return 1; } if (x1>0 && data[y1][x1 - 1] == old && lian_tong(data, len, y1, x1 - 1, y2, x2)) {
      data[y1][x1] = old;
      return 1;
    }
    if (x1 < len - 1 && data[y1][x1 + 1] == old && lian_tong(data, len,y1, x1 + 1, y2, x2))
    {
      data[y1][x1] = old;
      return 1;
    }
  data[y1][x1] = old;
  return 0;
}


void main1()
{
 
  /*int len = 0;
  scanf("%d", &len);
  char* *data = (char**)malloc(len*sizeof(char*));
  for (int i = 0; i < len; i++)
  {
  data[i] = (char*)malloc(len);
  memset(data[i], 0, len);
  scanf("%s", data[i]);
  }*/


  FILE*fp1 = fopen("1.txt", "r");

  int len = 0;
  char arr[10] = { 0 };  
  fgets(arr, 10, fp1);
  len=atoi(arr);
  printf("%d\n\n", len);

  char* *data = (char**)malloc(len*sizeof(char*));
  for (int i = 0; i < len; i++)
  {
    data[i] = (char*)malloc(len+2);
    memset(data[i], 0, len+2);
    char *pp = data[i];
    fgets(data[i], len+2, fp1);
    printf("%s", data[i]);
  }
  fclose(fp1);

  int m = 0;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) { char arr[1024] = { 0 }; char c; fflush(stdin); //while ((c = getchar()) != EOF && c != '\n');//不停地使用getchar()获取缓冲中字符,直到获取的c是“\n”或文件结尾符EOF为止 gets(arr); int shu[4] = { 0 }; int f1 = 0; int tail = 0; int f2 = 0; int flag = 1; while (flag>=0)
    {
      if (arr[f1] != ' '&&arr[f1] != '\0')
      {
        tail++;
      }
      else
      {
        char mp[1024] = { 0 };
        strncpy(mp, arr+f1-tail,tail);
        shu[f2] = atoi(mp);
        f2++;
        tail = 0;
      }      
      f1++;
      if (arr[f1] == '\0')
      {
        flag--;
      }
    }
    int x=lian_tong(data, len, shu[0], shu[1], shu[2], shu[3]);
    printf("%s\n", x ? "true" : "false");
  }
}


2. 迷宫问题
…11111111111111111111111111111
11.111111……..1111111111.1111
11.111111..111.11111111…..1111
11.11111111111.1111111111.111111
11.111111……………..111111
11.111111.11111111111.11111.1111
11.111111.11111111111.11111..111
11……….111111111.11111.1111
11111.111111111111111.11….1111
11111.111111111111111.11.11.1111
11111.111111111111111.11.11.1111
111…111111111111111.11.11.1111
111.11111111111111111….11.1111
111.11111111111111111111111.1111
111.1111.111111111111111……11
111.1111…….111111111.1111.11
111.1111.11111.111111111.1111.11
111……11111.111111111.1111111
11111111111111.111111111.111…1
11111111111111……………1.1
111111111111111111111111111111..

如上图的迷宫,入口,出口分别:左上角,右下角
“1”是墙壁,”.”是通路
求最短需要走多少步?

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

public class A
{
  // from: 出发位置  goal: 目标位置
  static int f(char[][] data, Set from, String goal){
    if(from.contains(goal)) return 0; // 起点与终点重合,需要0步
   
    Set set = new HashSet(); // 找到from的相邻连通点
   
    for(Object obj: from){
      String[] ss = ((String)obj).split(",");
      int y = Integer.parseInt(ss[0]);
      int x = Integer.parseInt(ss[1]);
     
      if(y>0 && data[y-1][x]=='.'){ data[y-1][x] = '*'; set.add(y-1+","+x); }
      if(y<data.length-1 && data[y+1][x]=='.'){ data[y+1][x] = '*'; set.add(y+1+","+x); } if(x>0 && data[y][x-1]=='.'){ data[y][x-1] = '*'; set.add(y+","+(x-1)); }
      if(x<data[0].length-1 && data[y][x+1]=='.'){ data[y][x+1] = '*'; set.add(y+","+(x+1)); }
    }
   
    if(set.isEmpty()) return -1;
    int r = f(data, set, goal);
    if(r<0) return -1;
    return r + 1;
  }
 
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
   
    String[] ss = scan.nextLine().trim().split(" +");
    int n = Integer.parseInt(ss[0]);
    int m = Integer.parseInt(ss[1]);
   
    char[][] data = new char[n][];
    for(int i=0; i<n; i++){
      data[i] = scan.nextLine().trim().toCharArray();
    }
   
    Set set = new HashSet();
    set.add("0,0");
    System.out.println(f(data, set, n-1 + "," + (m-1)));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//list.h
#ifndef LIST_H
#define LIST_H

#include <stdlib.h>

//定义基础的结构
typedef struct ListElmt_{
  void *data;
  struct ListElmt_ *next;
}ListElmt;

//定义列表
typedef struct list_{
  int size;//大小
  int(*match)(const void *key1, const void *key2);//比较,匹配
  void(*destroy)(void *data);//内存释放函数
  ListElmt *head;//头
  ListElmt *tail;//尾部
}List;

//初始化
void list_init(List *list, void(*destroy)(void *data));
//在element元素后插入一个元素,如果element为空,则插入链表头部
int list_ins_next(List *list, ListElmt *element, const void *data);
//删除element后面的那个元素,如果element为空,则删除链表头元素
int list_rem_next(List *list, ListElmt *element, void **data);
//删除一个列表,删除列表里面存储的data
void list_destroy(List *list);


//定义基础的宏,获取各种基础的数据:获取大小,头,尾部,判断是头,是尾,数据,下一个元素
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list,element) ((element) == (list)->head?1:0)
#define list_is_tail(element) ((element)->next == NULL?1:0)
#define list_data(element)((element)->data)
#define list_next(element)((element)->next)

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//list.c
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "list.h"


void list_init(List *list, void(*destroy)(void *data)){
  list->size = 0;

  list->destroy = destroy;
  list->head = list->tail = NULL;
  return;
}


//在element元素后插入一个元素,
//如果element为空,则插入链表头部
//需要考虑链表为空的情况
int list_ins_next(List *list, ListElmt *element, const void *data){
  //创建新数据
  ListElmt *new_element;
  if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
    return -1;
  new_element->data = (void *)data;
  new_element->next = NULL;
  //如果选定数据为空,插入到表头
  if (element == NULL){
    //如果列表为空,尾部也指向新元素
    if (list_size(list) == 0)
      list->tail = new_element;
    //在头链表前插入
    new_element->next = list->head;
    list->head = new_element;
  }
  else{
    //如果是最后一个元素
    if (element->next == NULL)
      list->tail = new_element;
    //在元素后插入
    new_element->next = element->next;
    element->next = new_element;
  }
  list->size++;
  return 0;
}

//删除element后面的那个元素
//如果element为空,则删除链表头元素
int list_rem_next(List *list, ListElmt *element, void **data){

  //队列不为空
  if (list_size(list) == 0){
    return -1;
  }
  ListElmt *old_element;

  if (element == NULL){
    //头部删除一个元素
    *data = list->head->data;
    old_element = list->head;

    list->head = list->head->next;
    if (list_size(list) == 1) {
      list->tail = NULL;
    }
  }
  else{
    //尾部删除一个元素
    if (element->next == NULL){
      return -1;
    }
    *data = element->next->data;
    old_element = element->next;
    element->next = element->next->next;
    if (element->next == NULL){
      list->tail = element;
    }
  }
  free(old_element);
  list->size--;
  return 0;
}


//删除一个列表,删除列表里面存储的data
void list_destroy(List *list){
  void *data;
  while (list_size(list) > 0){
    if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL){
      list->destroy(data);
    }
  }
  memset(list, 0, sizeof(List));
  return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//
//  set.h
//  set
//
//  Created by bikang on 16/9/18.
//  Copyright (c) 2016年 bikang. All rights reserved.
//

#ifndef __set__set__
#define __set__set__

#include <stdlib.h>
#include "list.h"

typedef List Set;

void set_init(Set *set, int(*match)(const void *k1, const void *k2), void(*destroy)(void*data));
#define set_destroy list_destroy
//插入
int set_insert(Set *set, const void *data);
//删除
int set_remove(Set *set, void **data);
//并集
int set_union(Set *setu, const Set *set1, const Set *set2);
//交集
int set_intersection(Set *seti, const Set *set1, const Set *set2);
//差集
int set_difference(Set *setd, const Set *set1, const Set *set2);
//是否是他的成员
int set_is_member(const Set *set, const void *data);
//是否是子集
int set_is_subset(const Set *set1, const Set *set2);
//是否相等
int set_is_equal(const Set *set1, const Set *set2);

#define set_size(set) ((set)->size)
#endif /* defined(__set__set__) */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//  set.c
//  set
//
//  Created by bikang on 16/9/18.
//  Copyright (c) 2016年 bikang. All rights reserved.
//
#include <stdlib.h>
#include <string.h>

#include "set.h"


//初始化集合
void set_init(Set *set, int(*match)(const void *k1, const void *k2), void(*destroy)(void*data))
{
  list_init(set, destroy);
  set->match = match;
  return;
}

//插入数据
int set_insert(Set *set, const void *data)
{
  if (set_is_member(set, data)){
    return 1;
  }
  return list_ins_next(set, list_tail(set), data);
}

//删除数据
int set_remove(Set *set, void **data){

  ListElmt *item, *pre;
  pre = NULL;
  for (item = list_head(set); item != NULL; item = list_next(item)){
    if (set->match(*data, list_data(item))) break;
    pre = item;
  }
  if (item == NULL) return -1;
  return list_rem_next(set, pre, data);
}
//并集
int set_union(Set *setu, const Set *set1, const Set *set2){
  ListElmt *item;
  void *data;
  set_init(setu, set1->match, NULL);
  for (item = list_head(set1); item != NULL; item = list_next(item)){
    data = list_data(item);
    if (list_ins_next(setu, list_tail(setu), data) != 0){
      set_destroy(setu);
      return -1;
    }
  }

  for (item = list_head(set2); item != NULL; item = list_next(item)){
    data = list_data(item);
    if (!set_is_member(setu, list_data(item))){
      if (list_ins_next(setu, list_tail(setu), data) != 0){
        set_destroy(setu);
        return -1;
      }
    }
  }
  return 0;
}

//交集
int set_intersection(Set *seti, const Set *set1, const Set *set2){
  ListElmt *item;
  void *data;
  set_init(seti, set1->match, NULL);

  for (item = list_head(set1); item != NULL; item = list_next(item)){
    if (set_is_member(set2, list_data(item))){
      data = list_data(item);
      if (list_ins_next(seti, list_tail(seti), data) != 0){
        set_destroy(seti);
        return -1;
      }
    }
  }
  return 0;
}

//差集
int set_difference(Set *setd, const Set *set1, const Set *set2){
  ListElmt *item;
  void *data;
  set_init(setd, set1->match, NULL);

  for (item = list_head(set1); item != NULL; item = list_next(item)){
    if (!set_is_member(set2, list_data(item))){
      data = list_data(item);
      if (list_ins_next(setd, list_tail(setd), data) != 0){
        set_destroy(setd);
        return -1;
      }
    }
  }
  return 0;
}


//是否是他的成员
int set_is_member(const Set *set, const void *data){
  ListElmt *item;
  for (item = list_head(set); item != NULL; item = list_next(item)){
    if (set->match(data, list_data(item))) return 1;
  }
  return 0;
}

//set1是否是set2的子集
int set_is_subset(const Set *set1, const Set *set2){
  ListElmt *item;
  // set1
  if (set_size(set1) > set_size(set2)) return 0;
  for (item = list_head(set1); item != NULL; item = list_next(item)){
    if (!set_is_member(set2, list_data(item))) return 0;
  }
  return 1;
}

//是否相等
int set_is_equal(const Set *set1, const Set *set2){
  if (set_size(set1) != set_size(set2)) return 0;

  return set_is_subset(set1, set2);
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "set.h"
#include "list.h"

int match_data(const void *d1, const void *d2){
  if (*(int*)d1 == *(int*)d2) return 1;
  return 0;
}

int f(char* data[],int len, Set from, char* goal)
{
  Set *set2 = (Set*)malloc(sizeof(Set));
  Set *set3 = (Set*)malloc(sizeof(Set));
  set_init(set2, match_data, NULL);
  set_insert(set2, goal);
  if (set_is_subset((const Set *)&from, set2))
    return 0; // 起点与终点重合,需要0步

  set_init(set3, match_data, NULL); // 找到from的相邻连通点

  for (ListElmt *item = list_head(&from); item != NULL; item = list_next(item))
  {


    char*p1=strstr(item->data, ",");
    char akq[10] = { 0 };
    strncpy(akq, item->data, p1 - item->data);
    int y = atoi(akq);
    strcpy(akq, item->data, p1+1);
    int x = atoi(akq);
   
    if (y > 0 && data[y - 1][x] == '.')
    {
      data[y - 1][x] = '*';

      char *buf = (char*)malloc(1024);
      memset(buf, 0, 1024);
      _itoa(y - 1, buf, 10);
      char tmp[1024] = { 0 };
      _itoa(x, tmp, 10);
      strcat(buf, ",");
      strcat(buf, tmp);
      set_insert(set3, buf);
    }
    if (y<len - 1 && data[y + 1][x] == '.') { data[y + 1][x] = '*'; char *buf = (char*)malloc(1024); memset(buf, 0, 1024); _itoa(y + 1, buf, 10); char tmp[1024] = { 0 }; _itoa(x, tmp, 10); strcat(buf, ","); strcat(buf, tmp); set_insert(set3, buf); } if (x>0 && data[y][x - 1] == '.')
    {
      data[y][x - 1] = '*';
     
      char *buf = (char*)malloc(1024);
      memset(buf, 0, 1024);
      _itoa(y, buf, 10);
      char tmp[1024] = { 0 };
      _itoa(x - 1, tmp, 10);
      strcat(buf, ",");
      strcat(buf, tmp);
      set_insert(set3, buf);
    }

    char *pk = data[0];
    int xy=strlen(pk);
    if (x <xy - 1 && data[y][x + 1] == '.')
    {
      data[y][x + 1] = '*';
     
      char *buf = (char*)malloc(1024);
      memset(buf, 0, 1024);
      _itoa(y, buf, 10);
      char tmp[1024] = { 0 };
      _itoa(x + 1, tmp, 10);
      strcat(buf, ",");
      strcat(buf, tmp);
      set_insert(set3, buf);
    }
  }

  if (set_size(set3) == 0)
    return -1;
  int r = f(data, len, *set3, goal);
  if (r < 0)
    return -1;
  return r + 1;
}

void main2()
{
  FILE*fp1 = fopen("2.txt", "r");
  int n[2] = {0};
  int m = 0;
  char arr[10] = { 0 };  
  fgets(arr, 10, fp1);
  char* token = strtok(arr, " ");
  int len = 0;
  while (token != NULL)
  {
    n[len++]=atoi(token);
    token = strtok(NULL, " ");
  }

  char* *data = (char**)malloc(n[0]*sizeof(char*));
  for (int i = 0; i < n[0]; i++)
  {
    data[i] = (char*)malloc(n[1] + 2);
    memset(data[i], 0, n[1] + 2);
    fgets(data[i], n[1]+2, fp1);
    printf("%s", data[i]);
  }
  fclose(fp1);

 
  Set *set1 = (Set*)malloc(sizeof(Set));
  set_init(set1, match_data, NULL);
  char *pi = "0,0";
  set_insert(set1, pi);

  char *buf = (char*)malloc(1024);
  memset(buf, 0, 1024);
  _itoa(n[0] - 1, buf, 10);
  char tmp[1024] = { 0 };
  _itoa(n[1] - 1, tmp, 10);
  strcat(buf, ",");
  strcat(buf, tmp);

  char *ps = f(data, n[0], *set1, buf);
 
}


3. 分酒问题
有4个红酒瓶子,它们的容量分别是:9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0],也就是说:第一个瓶子满着,其它的都空着。

允许把酒从一个瓶子倒入另一个瓶子,但只能把一个瓶子倒满或把一个瓶子倒空,不能有中间状态。
这样的一次倒酒动作称为1次操作。

假设瓶子的容量和初始状态不变,对于给定的目标状态,至少需要多少次操作才能实现?
本题就是要求你编程实现最小操作次数的计算。

输入:最终状态(空格分隔)
输出:最小操作次数(如无法实现,则输出-1)

例如:
输入:
9 0 0 0
应该输出:
0

输入:
6 0 0 3
应该输出:
-1

输入:
7 2 0 0
应该输出:
2

测试用例:
输入:2,4,1,2
输出:6
输入:3,1,3,2
输出:9
输入:2,6,1,0
输出:7

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 图的节点就是状态,在运行中才产生
import java.util.*;
public class A
{
  // 当前状态的可达集合
  static Set move(String cur){
    int[] cap = {9,7,4,2};
    int[] data = new int[4];
    String[] ss = cur.split(" ");
    for(int i=0; i<4; i++) data[i] = Integer.parseInt(ss[i]);
   
    Set set = new HashSet();
    // 试着从i倒入j
    for(int i=0; i<4; i++)
    for(int j=0; j<4; j++){
      if(j==i) continue;
      if(data[i]==0) continue;  //源空
      if(data[j]==cap[j]) continue; //目标满了
     
      int sum = data[i]+data[j];  
      int vi = (sum <= cap[j])? 0 : sum - cap[j]; // 假如倒酒后,i号的新值
      int vj = (sum <= cap[j])? sum : cap[j];  // 假如倒酒后,j号的新值
 
      //生成新的状态串
      String s = "";
      for(int k=0; k<4; k++){
        if(k==i) s += vi + " ";
        else if(k==j) s += vj + " ";
        else s += data[k] + " ";
      }
     
      set.add(s.trim());
    }
   
    return set;
  }

  static int f(Set hist, Set from, String goal){
    if(from.contains(goal)) return 0;
   
    Set from2 = new HashSet();
    for(Object it: from){
      Set t = move(it.toString());
      from2.addAll(t);
    }
   
    from2.removeAll(hist);
    if(from2.isEmpty()) return -1;
   
    hist.addAll(from2);
    int r = f(hist, from2, goal);
    if(r<0) return r;
    return r + 1;
  }

  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
   
    Set from = new HashSet(); //出发态
    from.add("9 0 0 0");
    Set hist = new HashSet(); //所有历史态
    hist.addAll(from);
   
    System.out.println(f(hist,from,scan.nextLine().trim()));
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "set.h"
typedef struct Node
{
  int data[4];
  struct Node *pNext;
}Node;


typedef struct Link
{
  Node * pHeadOfNode;
  struct Link * pNext;
}Link;

//比较数组是否相同,相同返回1,不同返回0;
int cmp(int arr1[4], int len1, int arr2[4], int len2)
{
  if (len1!=len2)
  {
    return 0;
  }

  for (int i = 0; i < len1;i++) { if (arr1[i] != arr2[i]) { return 0; } } return 1; } //遍历链表中的节点,再遍历节点看看是否有于和goal相同的数组;有的话返回1,没有返回0 int contains(Link* from, int goal[4]) { Link*temp = from; while (temp) { Node *tempNode = temp->pHeadOfNode;
    while (tempNode)
    {
      int x=cmp(tempNode->data, 4, goal, 4);
      if (x)
      {
        return 1;
      }
      tempNode = tempNode->pNext;
    }
    temp = temp->pNext;
  }
  return 0;
}

void addAll(Link ** head, Link **temp, Link*p)
{
  if (*head==NULL)
  {
    *head = p;
    *temp = p;
  }
  else
  {
    (*temp)->pNext = p;
    *temp = p;
  }
}
void removeAll(Link *from, Link*hist1)
{

  while (from)
  {
    Node*pNode = from->pHeadOfNode;
    while (pNode)
    {      
          Link*hist = hist1;
          while (hist)
          {
            Node*phistNode = hist1->pHeadOfNode;
            while (phistNode)
            {
              int x=cmp(pNode->data, 4, phistNode->data, 4);
              if (x==1)
              {
                //from2里面的data和hist里面的data相同,则把from2里面的改为0000;
                memset(pNode->data, 0, 4 * sizeof(int));
                goto A;
              }
              phistNode = phistNode->pNext;
            }
            hist = hist->pNext;
          }
      pNode = pNode->pNext;
    }
A:    from = from->pNext;
  }
}



//一组数据,只倒一下,可以由多少张情况。例如9 0 0 0,可以获取多少种情况
Node* move(int cur[], int len)
{
  int cap[] = { 9, 7, 4, 2 };
  int data[4];
  for (int x = 0; x < 4; x++)
  {
    data[x] = cur[x];
  }

  Node* phead = NULL;
  Node* ptail = NULL;
  for (int i = 0; i < 4; i++)
  {
    Node* tep = NULL;
    for (int j = 0; j < 4; j++)
    {
      if (j == i)
        continue;
      if (data[i] == 0)
        continue;  //源空
      if (data[j] == cap[j])
        continue; //目标满了
      int sum = data[i] + data[j];
      int vi = (sum <= cap[j]) ? 0 : sum - cap[j]; // 假如倒酒后,i号的新值
      int vj = (sum <= cap[j]) ? sum : cap[j]; // 假如倒酒后,j号的新值 tep = malloc(1 * sizeof(Node)); tep->pNext = NULL;
      //生成新的状态串
      for (int k = 0; k < 4; k++) { if (k == i) tep->data[i] = vi;
        else if (k == j)
          tep->data[k] = vj;
        else
          tep->data[k] = data[k];
      }
      if (phead == NULL)
      {
        phead = tep;
        ptail = tep;
      }
      else
      {
        ptail->pNext = tep;
        ptail = tep;
      }
    }
   
  }
  return phead;
}


//hist 历史状态,from出发态
int ff(Link* hist, Link* from, int goal[4])
{
  //出发态链表中有索要求得状态时,返回0,表明不需要在进行查找了,本层就包含
  if (contains(from, goal))
  {
    return 0;
  }
  //定义一个由出发态得到的所有状态集合(链表)
  Link* from2=NULL;
  Link* from2tem = NULL;
  //遍历出发态,得到所有状态集合
  Link*temp = from;
  while (temp)
  {

    Node *tempNode = temp->pHeadOfNode;
    while (tempNode)
    {
      //如果数据为0 0 0 0,说明已经在历史数据里面,进行跳过
      int arr[4] = { 0, 0, 0, 0 };
      int x = cmp(tempNode->data, 4, arr, 4);
      if (x == 1)
      {
        goto B;
      }
      Node*k=move(tempNode->data,4);
      Link *lk = (Link *)malloc(sizeof(Link));
      lk->pHeadOfNode = k;
      lk->pNext = NULL;
      addAll(&from2, &from2tem,lk);

B:      tempNode = tempNode->pNext;
    }
    temp = temp->pNext;
  }
 

  removeAll(from2, hist);
  Link*kk = from2;
  Link * pttep;
  while (kk)
  {
    Node*tt = kk->pHeadOfNode;
    int art[4] = { 0 };
    while (tt)
    {
      if (cmp(tt->data, 4, art,4)==0)
      {
        goto K;
      }
      tt = tt->pNext;
    }
    kk = kk->pNext;
  }
  return -1;

K:  //添加到历史数据里面
  pttep = hist;
  while (pttep->pNext)
  {
    pttep = pttep->pNext;
  }
  addAll(&hist, &pttep, from2);
 
  Link*ph = from2;
 
  int r = ff(hist, from2, goal);
  if (r<0)
  {
    return r;
  }
  else
  {
    return r + 1;
  }
}


// 图的节点就是状态,在运行中才产生
// 当前状态的可达集合
void main()
{
  int cap[] = { 9, 7, 4, 2 };
  Link *pHead = NULL;

  int goal[4] = { 0 };
  for (int i = 0; i < 4; i++) { scanf("%d", goal+i); } Link*hist = (Link*)malloc(sizeof(Link));; hist->pNext = NULL;
  hist->pHeadOfNode = NULL;

  Node*p1 = (Node*)malloc(sizeof(Node));
  p1->data[0] = 9;
  p1->data[1] = 0;
  p1->data[2] = 0;
  p1->data[3] = 0;
  p1->pNext = NULL;
 
  hist->pHeadOfNode = p1;

  int x = ff(hist, hist, goal);
  printf("需要多少步:%d", x);

}


4. 风险度量

X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。
两个空间站间可能直接通信,也可能通过其它空间站中转。

对于两个站点x和y (x != y), 如果能找到一个站点z,使得:
当z被破坏后,x和y不连通,则称z为关于x,y的关键站点。

显然,对于给定的两个站点,关于它们的关键点的个数越多,通信风险越大。

你的任务是:已经网络结构,求两站点之间的通信风险度,即:它们之间的关键点的个数。

输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数,链路数。
空间站的编号从1到n。通信链路用其两端的站点编号表示。
接下来m行,每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。
最后1行,两个数u,v,代表被询问通信风险度的两个站点。

输出:一个整数,如果询问的两点不连通则输出-1.

例如:
用户输入:
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
则程序应该输出:
2

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
java选手注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
java选手注意:主类的名字必须是:Main,否则按无效代码处理。

c/c++选手注意: main函数需要返回0
c/c++选手注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
c/c++选手注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

提交程序时,注意选择所期望的语言类型和编译器类型。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
import java.util.*;
public class A
{
  static void fan_zu(int[][] re, int me, int goal){
    if(re[me][3] <= goal) return; re[me][3] = goal; fan_zu(re, re[me][2], goal); } static void dfs(List[] gr, int[][] re, int v1, int v2){ if(v1==v2) return; for(Object obj: gr[v1]){ int it = (Integer)obj; if(re[it][0] > 0){
        fan_zu(re,v1,re[it][1]);  // 更新整个家族的返祖级
        continue;
      }
     
      re[it][0] = 1;
      re[it][1] = re[v1][1]+1;
      re[it][2] = v1;
      re[it][3] = re[v1][1];
      dfs(gr,re,it,v2);
    }
  }
 
  static int solve(int[][] re, int root, int leaf){
    int sum = 0;
    int p = leaf;
    int min = re[p][3];  // 当前最高(小)返祖级
    while(true){
      int pa = re[p][2];
      System.out.println("pa " + pa);
      if(pa==0 || pa==root) break;
      if(re[pa][1] <= min) sum++;
      if(re[pa][3] < min) min = re[pa][3]; p = pa; } return sum; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String[] ss = scan.nextLine().trim().split(" "); int m = Integer.parseInt(ss[0]); //节点数 int n = Integer.parseInt(ss[1]); //边数 List[] gr = new List[m+1]; // 顶点 --> list(顶点)
    for(int i=0; i<gr.length; i++) gr[i] = new Vector(); int[][] re = new int[m+1][4]; // dfs生成树结果: 顶点 --> (可见性, 深度, 父节点, 最高返祖)
   
    for(int i=0; i<n; i++){
      ss = scan.nextLine().trim().split(" ");
      int v1 = Integer.parseInt(ss[0]);
      int v2 = Integer.parseInt(ss[1]);
      gr[v1].add(v2);
      gr[v2].add(v1);
    }
   
    ss = scan.nextLine().trim().split(" ");
    int a = Integer.parseInt(ss[0]);
    int b = Integer.parseInt(ss[1]);
   
    re[a][0] = 1;
    re[a][1] = 0;
    re[1][3] = 0;
    dfs(gr,re,a,b);
   
    System.out.println(solve(re,a,b));  
  }
 
  static void debug(int[][] re){
    for(int i=0; i<re.length; i++){
      System.out.println(i + ": " + re[i][0] + "," + re[i][1] + "," + re[i][2] + "," + re[i][3]);
    }
  }
}

import java.util.*;


class MyGraph{
  class DfsNode{
    public int vex;
    public int level;
    public List<Integer> child;
    public int parent;
    public List<Integer> back;  //返祖
    public int min_back;  // 最小返祖level
   
    public DfsNode(int v){
      vex = v;
      level = 0;
      child = new ArrayList<Integer>();
      parent = -1;
      back = new ArrayList<Integer>();
      min_back = Integer.MAX_VALUE;
    }
   
    public void dfs(int v, Map<Integer,DfsNode> vis){
      DfsNode node = vis.get(v);
      if(node==null){
        child.add(v);
        node = new DfsNode(v);
        node.level = level + 1;
        node.parent = vex;
        vis.put(v, node);
       
        List<Integer> lst = map.get(v);
        for(int it: lst){
          node.dfs(it, vis);
        }
       
        return;
      }
     
      if(node.vex == parent) return;
       
      back.add(node.vex);
    }
   
    public void f_min_back(Map<Integer,DfsNode> tree){
      int min = Integer.MAX_VALUE;
      for(int it: back){
        int l = tree.get(it).level;
        if(l<min) min = l;
      }
     
      for(int it: child){
        DfsNode dn = tree.get(it);
        dn.f_min_back(tree);
        if(dn.min_back < min) min = dn.min_back;
      }
     
      min_back = min;
    }
   
    public String toString(){
      return "("+vex+",l="+level+",p="+parent+")";
    }
   
    public int ge_num(DfsNode root, Map<Integer,DfsNode> vis){
      if(parent == root.vex) return 0;
     
      DfsNode p = vis.get(parent);
      return p.ge_num(root, vis) + (min_back<p.level? 0 : 1);
    }
  }
 
  private Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
 
  public void add(int v1, int v2){
    List<Integer> lst = map.get(v1);
    if(lst==null){
      lst = new ArrayList<Integer>();
      map.put(v1, lst);
    }
    lst.add(v2);
   
    lst = map.get(v2);
    if(lst==null){
      lst = new ArrayList<Integer>();
      map.put(v2, lst);
    }
    lst.add(v1);
  }
 
  public int ge_num(int v1, int v2){
    DfsNode root = new DfsNode(v1);
    List<Integer> lst = map.get(v1);
    Map<Integer,DfsNode> vis = new HashMap<Integer,DfsNode>();
    vis.put(v1, root);
   
    for(int it: lst){
      root.dfs(it, vis);
    }
   
    root.f_min_back(vis);
    DfsNode p = vis.get(v2);    
    return p.ge_num(root, vis);
  }
}

public class B
{
  public static void main(String[] args)
  {
    Scanner scan = new Scanner(System.in);
   
    MyGraph g = new MyGraph();
   
    String[] ss = scan.nextLine().trim().split(" ");
    int n = Integer.parseInt(ss[1]);
    for(int i=0; i<n; i++){
      ss = scan.nextLine().trim().split(" ");
      g.add(Integer.parseInt(ss[0]), Integer.parseInt(ss[1]));
    }
   
    ss = scan.nextLine().trim().split(" ");
    int a = Integer.parseInt(ss[0]);
    int b = Integer.parseInt(ss[1]);
   
    System.out.println(g.ge_num(a,b));    
  }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//mylist.h
#ifndef MYLIST_H
#define MYLIST_H

typedef struct myNode
{
    void * data;
    struct myNode *next;
} MyNode;

typedef struct myList
{
    MyNode * first;
    MyNode * last;
    int count;
    int (*equal)(void * a, void * b);
} MyList;

typedef struct myListIterator
{
    MyNode * p;
    int count;
    int allSize;
} MyListIterator;

//创建链表
MyList * createMyList();

//创建链表,带有相等参数,用于查找
MyList * createMySearchList(int(*equal)(void * a, void * b));

//释放链表
void freeMyList(MyList * list);

//插入在尾部
void myListInsertDataAtLast(MyList* const list, void* const data);

//插入在首部
void myListInsertDataAtFirst(MyList * const list, void* const data);

//插入
void myListInsertDataAt(MyList * const list, void* const data, int index);

//删除在尾部
void* myListRemoveDataAtLast(MyList* const list);

//删除在首部
void* myListRemoveDataAtFirst(MyList * const list);

//删除
void* myListRemoveDataAt(MyList* const list, int index);

//删除对象,返回是否删除成功
int myListRemoveDataObject(MyList* const list, void * data);

//长度
int myListGetSize(const MyList * const list);

//打印
void myListOutput(const MyList * const list, void(*pt)(const void * const));

//取得数据
void* myListGetDataAt(const MyList * const list, int index);

//取得第一个数据
void* myListGetDataAtFirst(const MyList * const list);

//取得最后一个数据
void* myListGetDataAtLast(const MyList * const list);

//查找某个数据的位置,如果equal方法为空,比较地址,否则调用equal方法
//如果不存在返回-1,如果存在,返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, void * data);

//创建遍历器
MyListIterator* createMyListIterator(const MyList * const list);

//释放遍历器
void freeMyListIterator(MyListIterator* iterator);

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator);

//返回遍历器的下一个元素
void * myListIteratorNext(MyListIterator* const iterator);

#endif // MYLIST_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
//mylist.cpp
#include "mylist.h"

#include<malloc.h>
#include<stdlib.h>

//创建链表
MyList * createMyList()
{
    MyList * re = (MyList *) malloc(sizeof(MyList));
    re->count = 0;
    re->first = NULL;
    re->last = NULL;
    re->equal = NULL;
    return re;
}

//释放链表
void freeMyList(MyList * list)
{
    MyNode * p;
    while (list->first)
    {
        p = list->first->next;
        free(list->first);
        list->first = p;
    }
    free(list);
}

//插入在尾部
void myListInsertDataAtLast(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;
    if (list->count)
    {
        list->last->next = node;
        list->last = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//插入在首部
void myListInsertDataAtFirst(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    if (list->count)
    {
        node->next = list->first;
        list->first = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//长度
int myListGetSize(const MyList * const list)
{
    return list->count;
}

//打印
void myListOutput(const MyList * const list, void(*pt)(const void * const))
{
    MyNode * p = list->first;
    while (p)
    {
        (*pt)(p->data);
        p = p->next;
    }
}

//删除在尾部
void* myListRemoveDataAtLast(MyList* const list)
{
    if (list->count == 1)
    {
        return myListRemoveDataAtFirst(list);
    }
    MyNode * p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }
    void *re = list->last->data;
    free(list->last);
    p->next = NULL;
    list->last = p;
    (list->count)--;
    return re;
}

//删除在首部
void* myListRemoveDataAtFirst(MyList * const list)
{
    MyNode *p = list->first;
    list->first = p->next;
    void * re = p->data;
    free(p);
    (list->count)--;
    if (list->count == 0)
    {
        list->last = NULL;
    }
    return re;
}

//插入
void myListInsertDataAt(MyList * const list, void* const data, int index)
{
    if (index == 0)
    {
        myListInsertDataAtFirst(list, data);
        return;
    }
    if (index == list->count)
    {
        myListInsertDataAtLast(list, data);
        return;
    }
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++) { p = p->next;
    }
    node->next = p->next;
    p->next = node;

    (list->count)++;
}

//删除
void* myListRemoveDataAt(MyList* const list, int index)
{
    if (index == 0)
    {
        return myListRemoveDataAtFirst(list);
    }
    if (index == list->count - 1)
    {
        return myListRemoveDataAtLast(list);
    }

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++) { p = p->next;
    }
    MyNode *tp = p->next;
    p->next = p->next->next;
    void * re = tp->data;
    free(tp);
    (list->count)--;
    return re;
}

//取得数据
void* myListGetDataAt(const MyList * const list, int index)
{
    if (index == list->count - 1)
    {
        return myListGetDataAtLast(list);
    }
    MyNode * p = list->first;
    for (int i = 0; i < index; i++) { p = p->next;
    }
    return p->data;
}

//取得第一个数据
void* myListGetDataAtFirst(const MyList * const list)
{
    return list->first->data;
}

//取得最后一个数据
void* myListGetDataAtLast(const MyList * const list)
{
    return list->last->data;
}

//查找某个数据的位置,如果equal方法为空,比较地址,否则调用equal方法
//如果不存在返回-1,如果存在,返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, void * data)
{
    MyNode * p = list->first;
    int re = 0;
    if (list->equal)
    {
        while (p)
        {
            if (p->data == data || (*(list->equal))(p->data, data))
            {
                return re;
            }
            re++;
            p = p->next;
        }

    }
    else
    {
        while (p)
        {
            if (p->data == data)
            {
                return re;
            }
            re++;
            p = p->next;
        }
    }
    return -1;
}

//创建链表,带有相等参数,用于查找
MyList * createMySearchList(int(*equal)(void * a, void * b))
{
    MyList * re = createMyList();
    re->equal = equal;
    return re;
}

//创建遍历器
MyListIterator* createMyListIterator(const MyList * const list)
{
    MyListIterator * re = (MyListIterator *) malloc(sizeof(MyListIterator));
    re->p = list->first;
    re->allSize = list->count;
    re->count = 0;
    return re;
}

//释放遍历器
void freeMyListIterator(MyListIterator* iterator)
{
    free(iterator);
}

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator)
{
    return iterator->count < iterator->allSize;
}

//返回遍历器的下一个元素
void * myListIteratorNext(MyListIterator* const iterator)
{
//    if (iterator->p  == NULL)
//        return NULL;
    void * re = iterator->p->data;
    iterator->p = iterator->p->next;
    (iterator->count)++;
    return re;
}

//删除对象,返回是否删除成功
int myListRemoveDataObject(MyList* const list, void * data)
{
    MyListIterator * it = createMyListIterator(list);
    int a = 0;
    while (myListIteratorHasNext(it))
    {
        void * ld = myListIteratorNext(it);
        if (data == ld || (list->equal != NULL && (*(list->equal))(ld, data)))
        {
            a = 1;
            break;
        }
    }
    if (a)
    {
        myListRemoveDataAt(list, it->count - 1);
    }
    return a;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//mymap.h
#ifndef MYMAP_H
#define MYMAP_H

#include "mylist.h"

#define DEFAULT_INITIAL_CAPACITY 16
#define DEFAULT_LOAD_FACTOR 0.75f

typedef struct entry
{
    void * key;
    void * value;
} Entry;

typedef struct myHashMap
{
    int size;   //大小
    int initialCapacity; //初始容量
    float loadFactor;    //加载因子
    int (*hashCode)(void *key);
    int (*equal)(void *key1,void *key2);
    MyList ** entryList;
} MyHashMap;

typedef struct myHashMapEntryIterator
{
    int index;       //第几个链表
    MyHashMap *map;
    MyNode *current;
    int count;        //第几个数据
} MyHashMapEntryIterator;

//创建HashMap
MyHashMap *createMyHashMap(int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));

//使用全部参数创建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));

//释放HashMap
void freeMyHashMap(MyHashMap * map);

//是否包含某个key
int myHashMapContainsKey(MyHashMap *const map,void * const key);

//增加一条映射
void myHashMapPutData(MyHashMap *const map,void * const key,void * const value);

//通过key得到数据,如果没有数据则返回null
void* myHashMapGetDataByKey(MyHashMap * const map,void *const key);

//数据的容量
int myHashMapGetSize(const MyHashMap * const map);

//创建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator( MyHashMap *const map);

//释放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator);

//Entry迭代器是否有下一个
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator);

//遍历下一个Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator);

//删除一条数据,返回是否删除成功
int myHashMapRemoveDataByKey(MyHashMap *const map,void * const key);

//遍历
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*));

#endif // MYMAP_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
//mymap.cpp
#include "myMap.h"
#include <stdlib.h>

//某条Entry链表上是否包含某个key值。
Entry* listContainsEntry(MyList * list, void * key,
        int(*equal)(void *key1, void *key2))
{
    MyListIterator* it = createMyListIterator(list);
    while (myListIteratorHasNext(it))
    {
        Entry * entry = (Entry *) (myListIteratorNext(it));
        if (entry->key == key || (equal != NULL && (*equal)(entry->key, key)))
        {
            return entry;
        }
    }
    freeMyListIterator(it);
    return NULL;
}

void rebuildMyHashMap(MyHashMap * map)
{
    int newSize = map->initialCapacity * 2;
    MyList **newentryList = (MyList **) malloc(sizeof(MyList*) * newSize);
    for (int i = 0; i < newSize; i++) { newentryList[i] = createMyList(); } MyHashMapEntryIterator* it = createMyHashMapEntryIterator(map); while (myHashMapEntryIteratorHasNext(it)) { Entry * entry = myHashMapEntryIteratorNext(it); int hasCode = (*(map->hashCode))(entry->key);
        hasCode %= newSize;
        if (hasCode < 0)
            hasCode += newSize;
        myListInsertDataAtLast(newentryList[hasCode], entry);
    }
    freeMyHashMapEntryIterator(it);
    for (int i = 0; i < map->initialCapacity; i++)
    {
        freeMyList(map->entryList[i]);
    }
    free(map->entryList);
    map->entryList = newentryList;
    map->initialCapacity = newSize;
}

//创建HashMap
MyHashMap *createMyHashMap(int(*hashCode)(void *key),
        int(*equal)(void *key1, void *key2)) {
    MyHashMap *re = (MyHashMap *) malloc(sizeof(MyHashMap));
    re->size = 0;
    re->loadFactor = DEFAULT_LOAD_FACTOR;
    re->initialCapacity = DEFAULT_INITIAL_CAPACITY;
    re->entryList = (MyList **) malloc(sizeof(MyList*) * re->initialCapacity);
    re->hashCode = hashCode;
    re->equal = equal;
    for (int i = 0; i < re->initialCapacity; i++)
    {
        re->entryList[i] = createMyList();
    }
    return re;
}

//使用全部参数创建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity, float loadFactor,
        int(*hashCode)(void *key), int(*equal)(void *key1, void *key2))
{
    MyHashMap *re = createMyHashMap(hashCode, equal);
    re->initialCapacity = initialCapacity;
    re->loadFactor = loadFactor;
    return re;
}

//是否包含某个key
int myHashMapContainsKey(MyHashMap * const map, void * const key)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
    return re != NULL;
}

//增加一条映射
void myHashMapPutData(MyHashMap * const map, void * const key,
        void * const value)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
    if (re == NULL)
    {
        Entry * entry = (Entry*) malloc(sizeof(Entry));
        entry->key = key;
        entry->value = value;
        myListInsertDataAtLast(map->entryList[hasCode], entry);
        (map->size)++;
        if (map->size > map->initialCapacity * map->loadFactor)
        {
            rebuildMyHashMap(map);
        }
    } else
    {
        re->value = value;
    }
}

//通过key得到数据,如果没有数据则返回null
void* myHashMapGetDataByKey(MyHashMap * const map, void * const key)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
    if (re == NULL)
    {
        return NULL;
    }
    return re->value;
}

//数据的容量
int myHashMapGetSize(const MyHashMap * const map)
{
    return map->size;
}

//创建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator(MyHashMap * const map)
{
    MyHashMapEntryIterator* re = (MyHashMapEntryIterator*) malloc(
            sizeof(MyHashMapEntryIterator));
    re->count = 0;
    re->index = 0;
    re->map = map;
    re->current = map->entryList[0]->first;
    return re;
}

//释放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator)
{
    free(iterator);
}

//Entry迭代器是否有下一个
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator)
{
    return iterator->count < iterator->map->size;
}

//遍历下一个Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator)
{
    (iterator->count)++;
    while (!(iterator->current))
    {
        (iterator->index)++;
        iterator->current = iterator->map->entryList[iterator->index]->first;
    }
    Entry * re = (Entry *) iterator->current->data;
    iterator->current = iterator->current->next;
    return re;
}

//删除一条数据,返回是否删除成功
int myHashMapRemoveDataByKey(MyHashMap * const map, void * const key)
{
    int hasCode = (*(map->hashCode))(key);
    hasCode %= map->initialCapacity;
    if (hasCode < 0) hasCode += map->initialCapacity;
    MyListIterator* it = createMyListIterator(map->entryList[hasCode]);
    int re = 0;
    while (myListIteratorHasNext(it))
    {
        Entry * entry = (Entry *) (myListIteratorNext(it));
        if ((*(map->equal))(entry->key, key))
        {
            myListRemoveDataAt(map->entryList[hasCode], it->count - 1);
            re = 1;
            (map->size)--;
            break;
        }
    }
    freeMyListIterator(it);
    return re;
}

void myFree(Entry * p)
{
    free(p);
}

//释放HashMap
void freeMyHashMap(MyHashMap * map)
{
    myHashMapOutput(map, myFree);
    for (int i = 0; i < map->initialCapacity; i++)
    {
        freeMyList(map->entryList[i]);
    }
    free(map->entryList);
    free(map);
}

//遍历
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*))
{
    MyHashMapEntryIterator* iterator = createMyHashMapEntryIterator(map);
    while (myHashMapEntryIteratorHasNext(iterator))
    {
        pt(myHashMapEntryIteratorNext(iterator));
    }
    freeMyHashMapEntryIterator(iterator);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
//main.cpp
#include<stdio.h>
#include<stdlib.h>

#include "mylist.h"
#include "mymap.h"

//int类型hashCode
int myHashCodeInt(void * a)
{
    int * aa = (int *) a;
    return *aa;
}

//int类型相等的方法
int myEqualInt(void * a, void *b)
{
    int *aa = (int*) a;
    int *bb = (int *) b;
    return *aa == *bb;
}

MyHashMap * map = NULL;

struct DfsNode
{
    int vex;
    int level;
    MyList * child;
    int parent;
    MyList * back;
    int min_back;
};

void creatDfs(DfsNode* node, int v)
{
    node->vex = v;
    node->level = 0;
    node->child = createMyList();
    node->parent = -1;
    node->back = createMyList();
    node->min_back = __INT_MAX__;
}

void dfs(DfsNode* node, int v, MyHashMap * vis)
{
    DfsNode * tmpNode = (DfsNode*)myHashMapGetDataByKey(vis, (void*)(&v));
    if(tmpNode == NULL)
    {
        int * pV = (int *)malloc(sizeof(int));
        *pV = v;

        int * pV2 = (int *)malloc(sizeof(int));
        *pV2 = v;

        myListInsertDataAtLast(node->child, (void*)(pV));

        tmpNode = (DfsNode*)malloc(sizeof(DfsNode));
        creatDfs(tmpNode, v);
        tmpNode->level = node->level + 1;
        tmpNode->parent = node->vex;

        myHashMapPutData(vis, (void*)pV2, (void*)(tmpNode));

        MyList * lst = (MyList*)myHashMapGetDataByKey(map, (void*)(&v));

        if(lst)
        {
            // 遍历
            MyListIterator * it = createMyListIterator(lst);
            while(myListIteratorHasNext(it))
            {
                int * p = (int *)myListIteratorNext(it);

                dfs(tmpNode, *p, vis);
            }
            //释放迭代器
            freeMyListIterator(it);
        }

        return;
    }

    if(tmpNode->vex == node->parent)
        return;
    int * pVex = (int *)malloc(sizeof(int));
    *pVex = tmpNode->vex;
    myListInsertDataAtLast(node->back, (void*)pVex);
}

void f_min_back(DfsNode* node, void * tree)
{
    int min = __INT_MAX__;

    MyHashMap* pTree = (MyHashMap*)tree;

    // 遍历
    if(node && pTree && node->back)
    {
        MyListIterator * it = createMyListIterator(node->back);
        while(myListIteratorHasNext(it))
        {
            int * pValue = (int*)myListIteratorNext(it);
            DfsNode * tmpNode =
                    (DfsNode *)myHashMapGetDataByKey(pTree, (void*)pValue);

            if(tmpNode)
            {
                int l = tmpNode->level;
                if(l < min) min = l; } } //释放迭代器 freeMyListIterator(it); } if(node && pTree && node->child)
    {
        // 遍历
        MyListIterator * it = createMyListIterator(node->child);
        while(myListIteratorHasNext(it))
        {
            int * pValue = (int*)myListIteratorNext(it);
            DfsNode * tmpNode =
                    (DfsNode *)myHashMapGetDataByKey(pTree, (void*)pValue);

            if(tmpNode)
            {
                f_min_back(tmpNode, tree);
                if(tmpNode->min_back < min) min = tmpNode->min_back;
            }
        }
        //释放迭代器
        freeMyListIterator(it);
    }
    node->min_back = min;
}

int dfs_ge_num(DfsNode* node, DfsNode * root, void * vis)
{
    if(node->parent == root->vex) return 0;

    DfsNode * p =
            (DfsNode *)myHashMapGetDataByKey((MyHashMap*)vis, (void*)(&node->parent));
    return dfs_ge_num(p, root, vis) + ((node->min_back < p->level) ? 0 : 1);
}

void add(int v1, int v2)
{
    int * pV1 = (int *)malloc(sizeof(int));
    int * pV2 = (int *)malloc(sizeof(int));

    *pV1 = v1;
    *pV2 = v2;

    MyList * lst =
            (MyList *)myHashMapGetDataByKey(map, (void*)(pV1));

    if(lst == NULL)
    {
        lst = createMyList();
        myHashMapPutData(map, (void*)(pV1), (void*)lst);
    }
    myListInsertDataAtLast(lst, (void*)(pV2));

    lst = (MyList *)myHashMapGetDataByKey(map, (void*)(pV2));
    if(lst == NULL)
    {
        lst = createMyList();
        myHashMapPutData(map, (void*)(pV2), (void*)lst);
    }
    myListInsertDataAtLast(lst, (void*)(pV1));
}

int ge_num(int v1, int v2)
{
    DfsNode * root = (DfsNode*)malloc(sizeof(DfsNode));
    creatDfs(root, v1);

    int * pV1 = (int *)malloc(sizeof(int));
    *pV1 = v1;
    MyList * lst = (MyList *)myHashMapGetDataByKey(map, (void*)(&v1));

    MyHashMap * vis = createMyHashMap(myHashCodeInt, myEqualInt);
    myHashMapPutData(vis, (void*)(pV1), (void*)root);

    if(lst)
    {
        // 遍历
        MyListIterator * it = createMyListIterator(lst);
        while(myListIteratorHasNext(it))
        {
            int * pValue = (int*)myListIteratorNext(it);
            dfs(root, *pValue, vis);
        }
        //释放迭代器
        freeMyListIterator(it);
    }

    f_min_back(root, (void*)vis);
    int * pV2 = (int *)malloc(sizeof(int));
    *pV2 = v2;
    DfsNode * p = (DfsNode *)myHashMapGetDataByKey(vis, (int*)(pV2));
    return dfs_ge_num(p, root, vis);
}

int main(/*int argc, char *argv[]*/)
{
    printf("%s", "Hello World!\n");
    map = createMyHashMap(myHashCodeInt, myEqualInt);

    int m, n, a, b = 0;

    scanf("%d %d", &m, &n);

    for(int i = 0; i < n; i++)
    {
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    scanf("%d %d", &a, &b);
    printf("%d", ge_num(a, b));

    return 0;
}


如果您需要更多课程内容和讲解视频,请联系小蓝


Spread the word. Share this post!

Leave Comment

电子邮件地址不会被公开。 必填项已用*标注