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;↵
}↵
~~~~~↵
↵
↵
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↵
↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵