如何通过递归解决呢？ [英] How to solve this by recursion?

问题描述

我需要通过递归来解决这个问题。

I required some help in solving this question by recursion.

问题：

一个懒惰的游客想要尽可能多地游览城市中有趣的地方，而不必比实际需要更进一步。从他位于城市西北角的旅馆开始，他打算散步至城市的东南角，然后向后走。当走到东南角时，他只会向东或向南走，而走回西北角时，他只会向北或向西走。在研究了城市地图后，他意识到任务并不是那么简单，因为某些区域被封锁了。因此，他恳请您编写一个程序来解决他的问题。

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.

*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........

答案：7。

我最初的想法是分两个部分解决这个问题。

My initial thoughts were to solve this problem in two parts.

1）当游客从左上角开始。

1) When the tourist starts from top-left corner.

2）当游客从右下角出发时。

2) When the tourist starts from down-right corner.

为答案添加两个部分，就是这样。

For the answer add them both parts, and that would be it.

这是第一部分的方法。

 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.

这里是问题链接： http://www.spoj.com/problems/TOURIST/

谢谢您的宝贵时间。

推荐答案

一些观察结果将帮助您更轻松地解决此问题：

A few observations will help you solve this problem more easily:

1. 在回程中，游客只能在网格中向左或向上移动。这等效于在第一次旅行中向右或向下移动。因此，
   两次旅行基本上没有区别。


2. 由于两次旅行基本相同，我们只需要考虑第一次旅行。从（0,0）
   单元格开始，我们可以同时发送2位游客。因此，我们的状态将由（x1，y1，x2，y2）组成，其中（x1，y1）是第一个游客的
   位置，而（x2，y2）是第二个游客在
   网格中的位置。


3. 每一步游客都可以向右或向下移动，所以我们有4个运动选择（每个游客2个选择）。


4. 如果两个游客都在同一个像元（x1 == x2和y1 == y2）上，如果该像元是特殊的，则只能加1。


5. 此算法的时间复杂度为O（n ^ 4）可能无法及时运行。我们可以将复杂度降低为O（n ^ 3）。如果我们知道第一个游客的
   位置是（x1，y1），第二个
   的x坐标是x2，那么我们必须具有x1 + y1 = x2 + y2，因为它们都覆盖相同的
   在相同时间内的距离。因此y2 = x1 + y1-x2，我们的状态仅取决于
   （x1，y1，x2）。

1. 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.
2. 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.
3. At each step either tourist can move right or down, so we have 4 choices for movement(2 choice for each tourist).
4. 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.
5. 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).

代码：

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

这篇关于如何通过递归解决呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！