Cod sursa(job #2192759)

Utilizator georgeromanGeorge Roman georgeroman Data 7 aprilie 2018 10:20:39
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <fstream>
#include <vector>

long flipRow(std::vector<std::vector<int>>& table, int row) {
  long oldSum = 0, newSum = 0;
  for (int j = 0; j < table[row].capacity(); j++) {
    oldSum += table[row][j];
    table[row][j] *= -1;
    newSum += table[row][j];
  }
  return newSum - oldSum;
}

long flipCol(std::vector<std::vector<int>>& table, int col) {
  long oldSum = 0, newSum = 0;
  for (int i = 0; i < table.capacity(); i++) {
    oldSum += table[i][col];
    table[i][col] *= -1;
    newSum += table[i][col];
  }
  return newSum - oldSum;
}

bool isValid(std::vector<int> stack, int size) {
  if (stack.size() >= size + 1) return false;
  if (stack[stack.size() - 1] >= size) return false;
  if (stack[stack.size() - 1] < 0) return false;
  if (stack.size() >= 2 && stack[stack.size() - 1] <= stack[stack.size() - 2]) return false;
  return true;
}

long backtrackRows(std::vector<std::vector<int>>& table, long currentSum, int n) {
  long maxSum = currentSum;
  std::vector<int> rowStack = std::vector<int>();
  rowStack.push_back(-1);
  while (rowStack.size() != 0) {
    bool found = false;
    if (rowStack[rowStack.size() - 1] >= 0) {
      currentSum += flipRow(table, rowStack[rowStack.size() - 1]);
    }
    while (rowStack[rowStack.size() - 1] < n) {
      rowStack[rowStack.size() - 1]++;
      if (isValid(rowStack, n)) {
        found = true;
        break;
      }
    }
    if (found) {
      currentSum += flipRow(table, rowStack[rowStack.size() - 1]);
      if (currentSum > maxSum) {
        maxSum = currentSum;
      }
      rowStack.push_back(-1);
    } else {
      flipCol(table, rowStack[rowStack.size() - 1]);
      rowStack.pop_back();
    }
  }

  return maxSum;
}

long backtrackCols(std::vector<std::vector<int>>& table, long currentSum, long (*backtrackRows)(std::vector<std::vector<int>>&, long, int), int n, int m) {
  long maxSum = currentSum;

  std::vector<int> colStack = std::vector<int>();
  colStack.push_back(-1);
  while (colStack.size() != 0) {
    bool found = false;
    if (colStack[colStack.size() - 1] >= 0) {
      currentSum += flipCol(table, colStack[colStack.size() - 1]);
    }
    while (colStack[colStack.size() - 1] < m) {
      colStack[colStack.size() - 1]++;
      if (isValid(colStack, m)) {
        found = true;
        break;
      }
    }
    if (found) {
      currentSum += flipCol(table, colStack[colStack.size() - 1]);
      if (currentSum > maxSum) {
        maxSum = currentSum;
      }
      long newSum = backtrackRows(table, currentSum, m);
      if (newSum > maxSum) {
        maxSum = newSum;
      }
      colStack.push_back(-1);
    } else {
      flipCol(table, colStack[colStack.size() - 1]);
      colStack.pop_back();
    }
  }

  return maxSum;
}

int main() {
  std::ifstream in("flip.in");
  std::ofstream out("flip.out");

  int n, m;
  in >> n >> m;

  std::vector<std::vector<int>> table = std::vector<std::vector<int>>();
  table.reserve(n);
  for (int i = 0; i < n; i++) {
    table[i] = std::vector<int>();
    table[i].reserve(m);
  }

  long currentSum = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      in >> table[i][j];
      currentSum += table[i][j];
    }
  }

  long max1 = backtrackCols(table, currentSum, backtrackRows, n, m);
  long max2 = backtrackRows(table, currentSum, n);
  out << (max1 > max2 ? max1 : max2);

  return 0;
}