递归解法(还差一个案例没过求解答)

求大家帮忙想想是哪里漏了情况没考虑。
算法为递归:
走到右下角
{//每走一步路径长加一,每回退一步减一
如果走到墙则回到上一个路点
如果走到已经走过的点则回到上一个路点
如果走到右下角则判断时候是否比最小记录更近,更近则更新最小记录
当前路口向上走
当前路口向下走
当前路口向左走
当前路口向右走
}
走回左下角
{//每找到项链记录加一,每从项链点回退则记录减一
如果走到墙则回到上一个路点
如果走到已经走过的点则回到上一个路点
如果走到左上角则判断时候是否比最大项链记录更大,更大则更新最大记录
当前路口向上走
当前路口向下走
当前路口向左走
当前路口向右走
}
代码如下:

#include <iostream>
#include <vector>
using namespace std;
class graph
{
private:
    vector<vector<char>> map;
    vector<vector<int>> map_temp;//用于递归实时记录上一个路口以及项链位置的临时地图
    int minRoad;
    int maxNecklace;
    int length, height;
    void GoPath(int m, int n);
    void ReturnPath(int m, int n);
public:
    graph(int m,int n);
    void Go() { GoPath(0,0); }
    void Back() {
        for (int i = 0; i < height; i++)
            for (int j = 0; j < length; j++)
            {
                if (map[i][j] == '1')
                    map_temp[i][j] = 1;
                else if (map[i][j] == '0')
                    map_temp[i][j] = 0;
                else
                    map_temp[i][j] = 99;
            }ReturnPath(height-1,length-1); }
    int getGoMin() { return minRoad; }
    int getMaxNeck() { return maxNecklace; }

};

graph::graph(int m, int n)
{
    length = n;
    height = m;
    map.resize(height);
    for (int i = 0; i < height; i++)
        map[i].resize(length);
    map_temp.resize(height);
    for (int i = 0; i < height; i++)
        map_temp[i].resize(length);
    for (int i = 0; i < height; i++)
        for (int j = 0; j < length; j++)
        {
            cin >> map[i][j];
        }
    for (int i = 0; i < height; i++)
        for (int j = 0; j < length; j++)
        {
            if (map[i][j] == '1')
                map_temp[i][j] = 1;
            else if (map[i][j] == '0')
                map_temp[i][j] = 0;
            else
                map_temp[i][j] = 99;
        }

    minRoad = 999;
    maxNecklace = 0;
}

void graph::GoPath(int m, int n)
{
    static int tempRoad = 0;
    tempRoad++;
    if (m < 0 || n < 0 || m >= height || n >= length)
    {//超出地图
        tempRoad--;
        return;
    }
    if (map_temp[m][n] == 1 || map_temp[m][n] == 2)
    {//撞墙回头,走过的地方回头
        tempRoad--;
        return;
    }
    if (m == height - 1 && n == length - 1)
    {//走到公主
        if (tempRoad < minRoad)
            minRoad = tempRoad-1;
        tempRoad--;
        return;
    }
    map_temp[m][n] = 2;//2表示已经走过的路径,防止走回头路
    GoPath(m, n + 1);//右走
    GoPath(m + 1, n);//左走
    GoPath(m, n - 1);//下走
    GoPath(m - 1, n);//上走
    map_temp[m][n] = 0;
    tempRoad--;
}

void graph::ReturnPath(int m, int n)
{
    static int tempNeck = 0;

    if (m < 0 || n < 0 || m >= height || n >= length)
        return;

    if (map_temp[m][n] == 1 || map_temp[m][n] == 2 || map_temp[m][n] == 3)
        return;//撞墙回头
    if (m == 0 && n == 0)
    {//到达目的地
        if (maxNecklace < tempNeck)
            maxNecklace = tempNeck;
        return;
    }
    if (map_temp[m][n] == 99)//99表示项链
    {
        tempNeck++;
        map_temp[m][n] = 3;//标记为3与2区分,如果从项链点回退,项链数量-1
    }
    else
        map_temp[m][n] = 2;

    ReturnPath(m, n + 1);
    ReturnPath(m + 1, n);
    ReturnPath(m, n - 1);
    ReturnPath(m - 1, n);
    if (map_temp[m][n] == 3)
        tempNeck--;
    map_temp[m][n] = 0;
}

int main()
{
    int m, n;
    cin >> m >> n;
    graph G(m, n);

    G.Go();
    G.Back();
    cout << G.getGoMin() << " " << G.getMaxNeck();
    system("pause");
    return 0;
}

0 条评论

目前还没有评论...

信息

难度
7
分类
(无)
标签
递交数
209
已通过
39
通过率
19%
被复制
8
上传者