I required some help in solving this question by recursion.
Question:
A lazy tourist wants to visit as many interesting locations in a city as possible without going one step further than necessary. Starting from his hotel, located in the north-west corner of city, he intends to take a walk to the south-east corner of the city and then walk back. When walking to the south-east corner, he will only walk east or south, and when walking back to the north-west corner, he will only walk north or west. After studying the city map he realizes that the task is not so simple because some areas are blocked. Therefore he has kindly asked you to write a program to solve his problem.
Given the city map (a 2D grid) where walkable areas are marked by ".", interesting locations are marked by "*", and blocked areas are marked by "#", determine the maximum number of interesting locations he can visit. Locations visited twice are only counted once.
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........
Ans : 7.
My initial thoughts were to solve this problem in two parts.
1) When the tourist starts from top-left corner.
2) When the tourist starts from down-right corner.
For the answer add them both parts, and that would be it.
Here's what the method looks like for the first part.
i and j were initially 0, 0.
path(int i, int j){
if(i == H && j == W){
return (strV[i][j] == '*')?1:0;
}
if(i >H || j >W || i<0 || j<0){
return 0;
}
if(visited[i][j] == 1){
//cout<<"vis";
return 0;
}
if(strV[i][j] == '#' ){
return 0;
}
visited[i][j] =1;
cout<<i<<" "<<j<<"\n";
// as i can go only down and right ,for the first part.
// south and east.
return max(path(i+1, j), path (i, j+1) ) + (strV[i][j] == '*')?1 :0;
}
Similarly I tried calculating for the second part.
As I've maintained the visited array, there is no possibility of revisiting the same point.
Hope that should satisfy the condition as they mention in the question.
I'm not sure if this will solve the question, it's giving incorrect answer.
Here's the question link: http://www.spoj.com/problems/TOURIST/
Thanks for your time.
A few observations will help you solve this problem more easily:
- In the return trip the tourist can only move left or up in the grid. This is equivalent to moving right or down in the first trip. So
basically there is no difference between the two trips.
- Since both trips are basically same we only need to think of first trip. We can send 2 tourists at the same time starting from (0,0)
cell. So our state will consist of (x1,y1,x2,y2) where (x1,y1) is
position of first tourist and (x2,y2) is position of second tourist in
grid.
- At each step either tourist can move right or down, so we have 4 choices for movement(2 choice for each tourist).
- If both tourists are on the same cell (x1==x2 and y1==y2) then we can add only 1 to result if that cell is special.
- This algorithm has time complexity of O(n^4) which won't probably run in time. We can reduce the complexity to O(n^3). If we know the
position of first tourist is (x1,y1) the x coordinate of second
tourist is x2 then we must have x1+y1=x2+y2 since they both cover same
distance in same amount of time. So y2=x1+y1-x2 and our state depends
only on (x1,y1,x2).
Code:
const int N 100+5
vector<string> board;
int dp[N][N][N]; // initialize with -1
int calc(int x1, int y1, int x2) {
int n=board.size(), m=board[0].size();
int y2=x1+y1-x2;
if(x1>=n || x2>=n || y1>=m || y2>=m) return 0; // out of range
if(board[x1][y1]=='#' || board[x2][y2]=='#') return 0; // path blocked so its an invalid move
if(dp[x1][y1][x2]!=-1) return dp[x1][y1][x2]; // avoid recalculation
int res=0;
if(board[x1][y1]=='*') res++;
if(board[x2][y2]=='*') res++;
if(board[x1][y1]=='*' && x1==x2 && y1==y2) res=1; // both tourist on same spot
int r=calc(x1+1, y1, x2); // first tourist down second tourist right
r=max(r, calc(x1+1, y1, x2+1)); // first tourist down second tourist down
r=max(r, calc(x1, y1+1, x2)); // first tourist right second tourist right
r=max(r, calc(x1, y1+1, x2+1)); // first tourist right second tourist down
res+=r;
dp[x1][y1][x2]=res; // memoize
return res;
}
Your approach has a few flaws. Some that make it give the wrong solution and some that are just lead to an inefficient search.
The flaws that lead to a wrong solution are:
- Adding the interesting locations on the best paths each way will not be a valid answer because you haven't discounted the interesting sights that you already visited one way from the path you took on the way back. (This will also just mean you're answer will just be double the one way number as the best path back would be the same path in reverse). You actually need to search your way back from the end of your way forward so you can properly account for the already visited
- Terminating the search in a block path with a value of 0. It needs to be highly penalized (at least H+V-2) so just reaching a block and giving up (not reaching the corner) won't be considered a valid path
- Not unvisiting the locations when you are backtracking. This will lead to not counting interesting locations that may have been visited in a different path than the one being evaluated
- Terminating on a visited location. There is nothing in the problem statement that prohibits crossing the same location twice. It can never happen when considering only one of the directions of travel anyway because you can only travel two directions that don't allow for going back on yourself
The flaw that leads to an inefficient search is not simplifying the search domain before searching for the best path. By creating a graph that only contains the interesting locations as nodes and connections between them when there is a valid (non-blocked) path between them you can decrease your search space considerably (depending on how sparse the interesting locations and abundant the blocks are)
Keeping as close to your attempt as possible my suggestions are:
- When visiting a location simply add one so you can unvisit it by removing one before returning your best path (just setting to zero may be a problem if you also do it in the search for the return path)
- When you reach the end of the path one way (i == H-1 && j == W-1, because you start at 0,0 not 1,1) do a similar search the other way keeping the visited location info
- Change your interesting location increase to (visited[i][j] == 0) && (strV[i][j] == '*') so you don't count interesting locations twice in the same path
- Penalise running into a block by returning at least -(H+V-2), but MIN_INT_VALUE or anything in between would also work
- Don't give up when you reach a location you already visited
Hope this is helpful
Here's a solution in JavaScript. It recursively tries all valid directions SE and NW, and saves its result if it's greater than the current max result.
function solve(grid) {
var maxVisited = 0;
var rows = grid.length;
var cols = grid[0].length;
// used to make a new copy of the visited set
function copy(obj) {
return JSON.parse(JSON.stringify(obj));
}
// used to test a current location returning false or the grid value
function move(r, c) {
if(r < 0 || c < 0 || r >= rows || c >= cols) { return false; }
if(grid[r][c] === "#") { return false; }
return grid[r][c];
}
// recursively solve the problem
function solveRec(r, c, grid, goBack, visited) {
// end trip, check if visited is greater than current max
if(goBack === true && r === 0 && c === 0) {
var count = Object.keys(visited).length;
if(count > maxVisited) { maxVisited = count; }
return;
}
var m = move(r, c);
// invalid move
if(m === false) { return; }
// place of interest, add to visited set
if(m === "*") { visited["" + r + ":" + c] = true; }
// try a move, if at S.E. go back home (turn around)
if(goBack === true || (r === rows-1 && c === cols-1)) {
// north west
solveRec(r-1, c, grid, true, copy(visited));
solveRec(r, c-1, grid, true, copy(visited));
} else {
// south east
solveRec(r+1, c, grid, false, copy(visited));
solveRec(r, c+1, grid, false, copy(visited));
}
}
solveRec(0, 0, grid, false, {});
return maxVisited;
}
console.log(solve([
"*........".split(""),
".....**#.".split(""),
"..**...#*".split(""),
"..####*#.".split(""),
".*.#*.*#.".split(""),
"...#**...".split(""),
"*........".split("")
])); // 7
EDIT Here's the jsfiddle http://jsfiddle.net/reeyws86/ You may want to add logic to avoid corner cases like when the grid is empty or only has 1 square.
