Hexagonal Grid : Challenge | Dynamic Programming | Algorithms | HackerRank

Hexagonal Grid : Challenge | Dynamic Programming | Algorithms | HackerRank
You are given a hexagonal grid of size 2xN. Your task is to construct the grid with 2x1 dominoes. The dominoes can be arranged in any of the three orientations shown below. To add to the woes, certain cells of the hexagonal grid are blackened i.e., no domino can occupy that cell. Can you construct such a hexagonal grid? The blackened cell and the 3 dominoes are shown in the figure below.

The easiest one is to just run a recursion, where in each step we will try to fill just two empty cells. The constraints are very small, so this solution works very fast. As an alternative solution you can write something like dynamic programming by submasks.


http://www.cnblogs.com/boring09/p/4493282.html

铺瓷砖的变种，做法也是类似

假设地板长下面这样，灰色的是无法填充的空洞，初始时可以把N块之外的地板填充成灰色的，便于边界处理

假设现在从后向前已经处理完了一部分，绿色的砖块代表已经遍历过了，蓝色虚线框代表已经计算完成的子问题

现在要遍历红色边框的地砖

只可能有两种铺法：

如果可以向下铺，很简单，递推到另一个子问题

如果向右铺，就有些麻烦了，又两种可能

第一种可能，有块灰色的砖，如下图所示，则规约成一个子问题

第二种可能，没有灰色的砖，下面也可以横着放，那么规约成另一个子问题

处理完这一步，就可以继续处理其他的砖了，也同样是类似的步骤

https://www.hackerrank.com/challenges/hexagonal-grid/editorial

int a[2][maxN];
int n;
bool fnd = false;

bool is_in(int i, int j) {
  return (0 <= i && i < 2 && j >= 0 && j < n);
}

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

void rec() {
  if (fnd) return;
  int change = false;
  for (int i = 0; i < 2 && !change && !fnd; ++i) {
    for (int j = 0; j < n && !change && !fnd; ++j) {
      if (a[i][j] == 0) {
        change = true;
        for (int k = 0; k < 3 && !fnd; ++k) {
          if (is_in(i + dx[k], j + dy[k]) && a[i + dx[k]][j + dy[k]] == 0) {
            a[i][j] = 1;
            a[i + dx[k]][j + dy[k]] = 1;
            rec();
            a[i][j] = 0;
            a[i + dx[k]][j + dy[k]] = 0;
          }
        }
      }
    }
  }
  if (!change) {
    fnd = true;
  }
}

void solve() {
  scanf("%d", &n);
  string s1, s2;
  cin >> s1 >> s2;

  for (int i = 0; i < n; ++i) {
    a[0][i] = s1[i] - '0';
    a[1][i] = s2[i] - '0';
  }

  fnd = false;
  rec();
  if (fnd) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Hexagonal Grids from Red Blob Games
Read full article from Hexagonal Grid : Challenge | Dynamic Programming | Algorithms | HackerRank