How to solve UVA 861 Little Bishops

Правка en5, от abhatter, 2020-12-05 07:30:45

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...

Thanks in advance

My solution as below

#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;
}
Теги #memoization, #backtracking, #recursion

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский 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 Английский abhatter 2020-12-31 00:19:53 1585
en5 Английский abhatter 2020-12-05 07:30:45 2 Tiny change: 'as below\n~~~~~\n#' -> 'as below\n\n~~~~~\n#'
en4 Английский abhatter 2020-12-05 07:30:11 20 Tiny change: 'dvance\n\n\n~~~~~\n#' -> 'dvance\n\nMy solution as below\n~~~~~\n#'
en3 Английский abhatter 2020-12-05 07:29:46 29
en2 Английский abhatter 2020-12-05 07:27:22 1537
en1 Английский abhatter 2020-12-05 07:26:14 535 Initial revision (published)