Guest User

Untitled

a guest
Aug 18th, 2019
79
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. using namespace std;
  4.  
  5. const int MAX = 25;
  6.  
  7. int t, d, w, k, result, num[MAX], map[MAX][MAX], data[MAX][MAX];
  8. bool flag, check[MAX];
  9.  
  10. bool checkK() {
  11. int cnt = 1, sum = 0;
  12.  
  13. for(int i=1;i<=w;i++) {
  14. int inx = data[1][i];
  15. cnt = 1;
  16.  
  17. for(int j=2;j<=d;j++) {
  18. if(data[j][i] == inx) cnt++;
  19. else {
  20. if(j == d - k + 2) break;
  21.  
  22. inx = data[j][i];
  23. cnt = 1;
  24. }
  25.  
  26. if(cnt >= k) {
  27. sum++;
  28. break;
  29. }
  30. }
  31.  
  32. if(sum != i) return false;
  33. }
  34.  
  35. return true;
  36. }
  37.  
  38. void getNum(int x, int n) {
  39. if(flag) return;
  40.  
  41. if(x == n) {
  42. if(checkK()) {
  43. result = n;
  44. flag = true;
  45. }
  46. }
  47. else {
  48. int arr[MAX] = {0,}, a_inx = 0;
  49.  
  50. for(int i=1;i<=d;i++) {
  51. if(!check[i]) {
  52. num[x] = i;
  53. check[i] = true;
  54. arr[a_inx++] = i;
  55.  
  56. for(int j=1;j<=w;j++) {
  57. data[num[x]][j] = 0;
  58. }
  59.  
  60. getNum(x+1, n);
  61.  
  62. for(int j=1;j<=w;j++) {
  63. data[num[x]][j] = 1;
  64. }
  65.  
  66. getNum(x+1, n);
  67.  
  68. for(int j=1;j<=w;j++) {
  69. data[num[x]][j] = map[num[x]][j];
  70. }
  71.  
  72. num[x] = 0;
  73. }
  74. }
  75.  
  76. for(int i=0;i<a_inx;i++) check[arr[i]] = false;
  77. }
  78. }
  79.  
  80. int main() {
  81. scanf("%d", &t);
  82.  
  83. for(int v=1;v<=t;v++) {
  84. scanf("%d %d %d", &d, &w, &k);
  85.  
  86. for(int i=1;i<=d;i++) {
  87. for(int j=1;j<=w;j++) {
  88. scanf("%d", &map[i][j]);
  89. data[i][j] = map[i][j];
  90. }
  91. }
  92.  
  93. if(k != 1) {
  94. if(!checkK()){
  95. int cnt =1;
  96. while(!flag) {
  97. getNum(0, cnt);
  98. cnt++;
  99. }
  100. for(int i=1;i<=d;i++) check[i] = false;
  101. }
  102. }
  103.  
  104. printf("#%d %d\n", v, result);
  105.  
  106. result = 0, flag = false;
  107.  
  108. for(int i=1;i<=d;i++) {
  109. for(int j=1;j<=w;j++) {
  110. map[i][j] = 0;
  111. data[i][j] = 0;
  112. }
  113. }
  114. }
  115.  
  116. return 0;
  117. }
RAW Paste Data