Am I using map wrong here?

Revision en1, by EugeneJudo, 2021-07-27 23:49:38

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;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English EugeneJudo 2021-07-27 23:49:38 2228 Initial revision (published)