SHARE
TWEET

Untitled

a guest Mar 20th, 2017 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> match, vis;
  6. vector<vector<int>> AdjList;
  7.  
  8. int Aug(int L) {
  9.   if (vis[L]) return 0;
  10.   vis[L] = 1;
  11.   for (int j = 0; j < (int)AdjList[L].size(); j++) {
  12.     int r = AdjList[L][j];
  13.     if (match[r] == -1) {
  14.       match[r] = L; return 1;
  15.     }
  16.   }
  17.   for (int j = 0; j < (int)AdjList[L].size(); j++) {
  18.     int r = AdjList[L][j];
  19.     if (Aug(match[r])) {
  20.       match[r] = L; return 1;
  21.     }
  22.   }
  23.   return 0;
  24. }
  25.  
  26. int tc, n, m;
  27. int grid[200][200];
  28. int wallsabove[200][200];
  29. int main() {
  30.   scanf("%d", &tc);
  31.   while (tc--) {
  32.     //memset(grid, 0, sizeof(grid));
  33.     //memset(wallsabove, 0, sizeof(wallsabove));
  34.     AdjList.clear();
  35.     match.clear();
  36.     vis.clear();
  37.     vector<int> rowsplits;
  38.     vector<int> colsplits;
  39.     scanf("%d %d", &n, &m);
  40.     for (int i = 0; i < m; i++) {
  41.       colsplits.push_back(1);
  42.     }
  43.     for (int i = 0; i < n; i++) {
  44.       int rCount = 1;
  45.       for (int j = 0; j < m; j++) {
  46.         scanf("%d", &grid[i][j]);
  47.         if (grid[i][j] == 2) {
  48.           if (j != 0 && grid[i][j-1] != 2) {
  49.             rCount++;
  50.           }
  51.           if (i == 0 || grid[i-1][j] == 2) {
  52.             wallsabove[i][j] = i == 0? 0 : wallsabove[i-1][j];
  53.           } else {
  54.             colsplits[j]++;
  55.             wallsabove[i][j] = i == 0? 1 : wallsabove[i-1][j] + 1;
  56.           }
  57.         } else {
  58.           wallsabove[i][j] = i == 0? 0 : wallsabove[i-1][j];
  59.         }
  60.       }
  61.       rowsplits.push_back(rCount);
  62.       if (i != 0) {
  63.         rowsplits[i] += rowsplits[i-1];
  64.       }
  65.     }
  66.     for (int i = 0; i < rowsplits[n-1]; i++) {
  67.       vector<int> tmp;
  68.       AdjList.push_back(tmp);
  69.     }
  70.     // Aggregate
  71.     for (int i = 1; i < m; i++) {
  72.       colsplits[i] += colsplits[i-1];
  73.     }
  74.  
  75.     for (int i = 0; i < n; i++) {
  76.       int prevRowsNodes = i == 0? 0 : rowsplits[i-1];
  77.       int walls = 0;
  78.       for (int j = 0; j < m; j++) {
  79.         if (grid[i][j] == 2) {
  80.           if (j != 0 & grid[i][j-1] != 2) walls++;
  81.         } else if (grid[i][j] == 1) {
  82.           continue;
  83.         } else {
  84.           int thisRNode = prevRowsNodes + walls;
  85.           int prevCNodes = j == 0? 0 : colsplits[j-1];
  86.           int wallsabv = wallsabove[i][j];
  87.           int thisCNode = rowsplits[n-1] + wallsabv + prevCNodes;
  88.           AdjList[thisRNode].push_back(thisCNode);
  89.           //printf("%d to %d\n", thisRNode, thisCNode);
  90.         }
  91.       }
  92.     }
  93.     int MCBM = 0;
  94.     match.assign(rowsplits[n-1]+colsplits[m-1],-1);
  95.     for (int L = 0; L < rowsplits[n-1]; L++) {
  96.       vis.assign(rowsplits[n-1],0);
  97.       MCBM += Aug(L);
  98.     }
  99.     printf("%d\n", MCBM);
  100.   }
  101.   return 0;
  102. }
RAW Paste Data
Top