Weekly Coding Contest TechZara 2020 - week3 - day 1

main.cpp

#include <bits/stdc++.h>

using namespace std;

// Compute score
int score(vector<vector<char>> board) {
  int h = board.size();
  int w = board[0].size();
  map<char, int> m;
  m['R'] = 0;
  m['G'] = 0;
  m['B'] = 0;
  m['Y'] = 0;
  m['O'] = 0;
  for (int i = 0; i < h - 1; i++) {
    for (int j = 0; j < w - 1; j++) {
      if (board[i][j] == board[i][j + 1]
          && board[i][j] == board[i + 1][j]
          && board[i][j] == board[i + 1][j + 1]) {
        m[board[i][j]]++;
      }
    }
  }
  return (m['R'] + 1)
    * (m['B'] + 1)
    * (m['G'] + 1)
    * (m['Y'] + 1)
    * (m['O'] + 1);
}

// Get edge coordinates for a rectangle (o: origin, h: height, w:width)
vector<pair<int, int>> edge_rect(pair<int, int> o, int h, int w) {
  
  vector<pair<int, int>> edge;
  // top side
  for (int i = 0; i < w; i++) {
    edge.push_back(make_pair(o.first, o.second + i));
  }
  // right side
  for (int i = 1; i < h; i++) {
    edge.push_back(make_pair(o.first + i, o.second + w - 1));
  }
  // bottom side
  for (int i = w - 2; i >= 0; i--) {
    edge.push_back(make_pair(o.first + h - 1, o.second + i));
  }
  // left side
  for (int i = h - 2; i >= 1; i--) {
    edge.push_back(make_pair(o.first + i, o.second));
  }
  return edge;
}

// rotate a rectangle (o:origin, h: height, w: width) n times
vector<vector<char>> rotate(vector<vector<char>> board, int n, pair<int, int> o,
  int w, int h) {
  // get the edge of the rectangle
  vector<pair<int, int>> e = edge_rect(o, w, h);
  // repeat n times
  while (n--) {
    char last = board[e[0].first][e[0].second];
    // rotate the edge of the rectangle
    for (int i = 0; i < e.size(); i++) {
      char t = board[e[(i + 1) % e.size()].first][e[(i + 1) % e.size()].second];
      board[e[(i + 1) % e.size()].first][e[(i + 1) % e.size()].second] = last;
      last = t;
    }
  }
  return board;
}

// main function
int TzWccS3BalsColor(std::vector<std::vector<char>> board, int k) {
  int h = board.size();
  int w = board[0].size();
  int total_score = 0;
  while (k--) {
    int max_score = INT_MIN;
    vector<vector<char>> max_board = board;
    for (int i = 0; i < h; i++) { // loop for rectangle's origin's y coordinage
      for (int j = 0; j < w; j++) { // loop for rectangle's origin's x coordinate
        for (int m = 1; m < h - i + 1; m++) { // all possible width of rectangle
          for (int l = 1; l < w - j + 1; l++) { // all possible length of rectangle
            for (int n = 1; n < 2 * m + 2 * l - 4; n++) { // all possible number of rotations = 2 * l + 2 * m - 4 (corners)
              vector<vector<char>> r = rotate(board, n, make_pair(i, j), m, l);
              int s = score(r);
              if (s > max_score) {
                max_score = s;
                max_board = r;
              }
            }
          }
        }
      }
    }
    total_score += max_score;
    board = max_board;
  }
  return total_score;
}

int main() {
  // test case 1
  vector<vector<char>> board = {{'B','B','G','O'},
                                {'R','B','B','O'},
                                {'Y','O','G','Y'}};
  int k = 2;
  cout << TzWccS3BalsColor(board, k) << "\n";
  return 0;
}