[刚剪的格子是什么样的视频]onlyblues

1 include

2 include

3 include

4 include

5 using namespace std;

6

7 typedef unsigned long long ULL;

8 typedef pairPII;

9

10 const int N=20, P=131;

11

12 int n, m, ans=N * N;

13 int graph[N][N];

14 bool vis[N][N];

15 int sum;

16 int fa[N * N];

17 PII a[N * N];

18 unordered_setst;

19 int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

20

21 int find(int x) {

22 return fa[x]==x ? fa[x] : fa[x]= find(fa[x]);

23 }

24

25 bool is_connect(int cnt) { // 判断剩余部分是否是一个连通块

26 for (int i=0; i < n * m; i++) {

27 fa[i]= i;

28 }

29

30 int num=n * m - cnt; // 一开始每一个未被剪得方格都是单独的一个连通块

31

32 // 遍历每一个方格

33 for (int i=0; i < n; i++) {

34 for (int j=0; j < m; j++) {

35 if (!vis[i][j]) { // 方格未被剪掉

36 for (int k=0; k < 4; k++) { // 往四个方向扩展

37 int x=i + dx[k], y=j + dy[k];

38 if (x >=0 && x < n && y >=0 && y < m && !vis[x][y]) {

39 int p1=find(x * m + y), p2=find(i * m + j); // 求这两个方格所在并查集的父节点

40 if (p1 !=p2) { // 这两个方格还不再同一个并查集中

41 fa[p1]=p2; // 把这两个合并，意味着这两个方格在同一个连通块

42 num--; // 连通块数量减1

43 }

44 }

45 }

46 }

47 }

48 }

49

50 return num==1; // 最后判断连通块数量是否只有一个

51 }

52

53 bool is_exist(int cnt) { // 判断某种情况是否已经搜过

54 PII tmp[N * N];

55 memcpy(tmp, a, sizeof(a)); // 因为要排序，会改变原集合中元素的顺序，因此进行备份

56

57 sort(tmp, tmp + cnt);

58

59 ULL key=0; // 这种情况的哈希值

60 for (int i=0; i < cnt; i++) {

61 key=key * P + tmp[i].first + 1; // 哈希不能有0，因为一个0和两个0得到的结果是一样的

62 key=key * P + tmp[i].second + 1;

63 }

64

65 if (st.count(key)) return true; // 如果这种情况出现过返回true

66 st.insert(key); // 否则这种情况未出现过，把这种情况加入哈希表中，返回false

67 return false;

68 }

69

70 void dfs(int cnt, int s) {

71 if (s > sum - s || cnt >=ans || !is_connect(cnt)) return; // 剪支

72 if (s==sum - s) {

73 ans= cnt;

74 return;

75 }

76

77 // 遍历集合中的每一个方格

78 for (int i=0; i < cnt; i++) {

79 int x=a[i].first, y= a[i].second;

80 for (int j=0; j < 4; j++) {

81 int xx=x + dx[j], yy=y + dy[j];

82 if (xx >=0 && xx < n && yy >=0 && yy < m && !vis[xx][yy]) {

83 a[cnt]= {xx, yy};

84 if (is_exist(cnt + 1)) continue; // 已经搜过的情况就不再搜了

85

86 vis[xx][yy]=true;

87 dfs(cnt + 1, s + graph[xx][yy]);

88 vis[xx][yy]=false;

89 }

90 }

91 }

92 }

93

94 int main() {

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

96 for (int i=0; i < n; i++) {

97 for (int j=0; j < m; j++) {

98 scanf("%d", &graph[i][j]);

99 sum += graph[i][j];

100 }

101 }

102

103 if (sum % 2==0) {

104 vis[0][0]=true;

105 a[0]={0, 0};

106 dfs(1, graph[0][0]);

107 }

108

109 printf("%d", ans==N * N ? 0 : ans);

110

111 return 0;

112 }