I'm a bit stumped at why my optimization to https://cses.fi/problemset/task/1625 is failing. With setting the map on line 73 commented out, the code (slowly) finds the correct answer. It seems conceptually that there shouldn't be an issue with using memoization, but i'm not so used to c++ maps. Can anyone see what's wrong?
#include <bits/stdc++.h>
using namespace std;
bool field[9][9] = {0};
int skip(int x, int y, int xp, int yp){
int dx = x-xp;
int dy = y-yp;
if(field[x+dx][y+dy] && !field[x+dy][y+dx] && !field[x-dy][y-dx]){
return true;
}
return false;
}
long long int getState(){
long long int x=0;
long long int ind=0;
for(int i=1;i<8;i++)
for(int j=1;j<8;j++){
if(field[i][j])
x += ((long long int)1<<(ind));
ind++;
}
return x;
}
int counter = 0;
map<long long int,int> m;
map<long long int,int>::iterator it;
int traverse(int x, int y, string s, int ind, int xp, int yp){
int t = 0;
if(field[x][y])
return 0;
if((ind + abs(x-7) + abs(y-1)) > 48)
return 0;
if((ind == 48) && (x==7) && (y==1)){
return 1;
}
else if((x==7) && (y==1))
return 0;
field[x][y] = true;
long long int state = getState();
it = m.find(state);
if(it!=m.end()){
field[x][y] = false;
return m[state];
}
if(!skip(x,y,xp,yp)){
if(s[ind] == 'U')
t += traverse(x-1,y,s,ind+1,x,y);
else if(s[ind] == 'D')
t += traverse(x+1,y,s,ind+1,x,y);
else if(s[ind] == 'L')
t += traverse(x,y-1,s,ind+1,x,y);
else if(s[ind] == 'R')
t += traverse(x,y+1,s,ind+1,x,y);
else{
t += traverse(x+1,y,s,ind+1,x,y);
t += traverse(x,y+1,s,ind+1,x,y);
t += traverse(x-1,y,s,ind+1,x,y);
t += traverse(x,y-1,s,ind+1,x,y);
}
}
if(ind < 10){
m[state] = t; //comment me out to work
}
field[x][y] = false;
return t;
}
int main(){
string s;
cin >> s;
for(int i=0;i<9;i++){
field[0][i] = true;
field[i][0] = true;
field[8][i] = true;
field[i][8] = true;
}
cout << traverse(1,1,s,0,0,1) << endl;
}
There are a couple of things wrong here. First, you're memorizing which squares you passed through, which is bad because you're not memorizing where you where when the memorization happened. Consider this:
xxxxxoo
oooxxoo
oooxxoo
ooooooo
Where is the place where you finished in this case? This is super important and for that you would need more states.
Second, memorization will not help you at all. If you do the backtracking starting from the start you are already storing the two states you need (which squares you passed through and what is your last square). There are other ways to try to optimize this brute force (like doing a dfs to see if it is still possible to reach the end square).
Also, an implementation trick: you had to do a lot of ifs because you were converting the characters to directions on the fly. Do the following: replace each character with a number from 0 to 3 and each '?' with 4. Then do to global arrays with something like, dx[]{1,0,-1,0}, dy[]{0,1,0,-1}. Now when you need to go to a direction you just need to check if the direction is 4, and otherwise you go to {x+dx[i], y+dy[i]}.