How to solve UVA 861 Little Bishops
Difference between en2 and en3, changed 29 character(s)
Hello,↵

I am learning to apply memoization technique but not able to figure it out. My brute force recursive back tracking solution gives correct answer but then times out quickly.↵
I tried to search answer to this question but then I am not able to understand anything.↵
could you please help me in this regards?↵
I have attached my solution↵


[
Problem link below
...](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=802)

Thanks in advance↵


~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

using row_t = vector<bool>;↵
using grid_t = vector<row_t>;↵

bool is_ok(const grid_t &grid, int p, int q) {↵
  for(int i = p-1, j = q-1; i >= 0 && j >= 0; --i, --j) {↵
    if(grid[i][j]) {↵
      return false;↵
    }↵
  }↵

  for(int i = p+1, j = q+1; ↵
      i < grid.size() && j < grid[i].size(); ++i, ++j) {↵
    if(grid[i][j]) {↵
      return false;↵
    }↵
  }↵

  for(int i = p-1, j = q+1; i >= 0 && j < grid[i].size();↵
      --i, ++j) {↵
    if(grid[i][j]) {↵
      return false;↵
    }↵
  }↵

  for(int i = p+1, j = q+1; ↵
      i < grid.size() && j < grid[i].size(); ++i, ++j) {↵
    if(grid[i][j]) {↵
      return false;↵
    }↵
  }↵
  return true;↵
}↵

void dfs(int p, int q, int k, ↵
         grid_t &grid, int &cnt, ↵
         int &total_cnt) {↵
  if(q == grid.size()) {↵
    q = 0;↵
    ++p;↵
  }↵

  for(int i = p; i < grid.size(); ++i) {↵
    for(int j = q; j < grid[i].size(); ++j) {↵
      grid[i][j] = true;↵
      if(is_ok(grid, i, j)) {↵
        ++cnt;↵
        if(cnt == k) {↵
          ++total_cnt;↵
        } else {↵
          dfs(i, j+1, k, grid, cnt, total_cnt);↵
        }↵
        --cnt;        ↵
      }↵
      grid[i][j] = false;↵
    }↵
    q = 0;↵
  }↵
}↵

int main() {↵
  while(true) {↵
    int n, k;↵
    cin >> n >> k;↵
    if(n == 0 && k == 0) {↵
      break;↵
    }↵

    grid_t grid(n, row_t(n, false));↵
    int cnt = 0;↵
    int total_cnt = 0;↵
    dfs(0,0, k, grid, cnt, total_cnt);↵
    cout << total_cnt << "\n";↵
  }↵
  return 0;↵
}

~~~~~↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English abhatter 2020-12-31 00:20:18 29 Tiny change: 'regards?\nI have attached my solution\n\n\n[Pro' -> 'regards?\n\n\n[Pro'
en6 English abhatter 2020-12-31 00:19:53 1585
en5 English abhatter 2020-12-05 07:30:45 2 Tiny change: 'as below\n~~~~~\n#' -> 'as below\n\n~~~~~\n#'
en4 English abhatter 2020-12-05 07:30:11 20 Tiny change: 'dvance\n\n\n~~~~~\n#' -> 'dvance\n\nMy solution as below\n~~~~~\n#'
en3 English abhatter 2020-12-05 07:29:46 29
en2 English abhatter 2020-12-05 07:27:22 1537
en1 English abhatter 2020-12-05 07:26:14 535 Initial revision (published)