算法-每天一道题（6）-拜访

现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。
给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。

测试样例：

[[0,1,0],[2,0,0]],2,3

返回：2

C++

class Visit {
public:
    int max(int a, int b)
    {
        if(a > b)
            return a;
        else
            return b;
    }
    int countPath(vector<vector<int> > map, int n, int m) {
        int start_x, start_y;
        int end_x, end_y;
        // 求解出出发点和目标点的坐标
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                if (map[i][j] == 1)
                {
                    start_x = i;
                    start_y = j;
                }
                if (map[i][j] == 2)
                {
                    end_x = i;
                    end_y = j;
                }
            }

        // 如果目标点或者出发点在同一个轴上，那么只有一种走法
        if (start_x == end_x || start_y == end_y)
            return 1;

        if (start_x < end_x)
            // 目标点在右下角，出发点在左上角
            if (start_y < end_y)
            {
                for (int i=end_x-1; i>=start_x; i--)
                    if (map[i][end_y] == -1)
                        break;
                    else
                        map[i][end_y] = 1;
                for (int i=end_y-1; i>=start_y; i--)
                    if (map[end_x][i] == -1)
                        break;
                    else
                        map[end_x][i] = 1;

                for (int i=end_x-1; i>=start_x; i--)
                    for (int j = end_y-1; j>=start_y; j--)
                        if (map[i+1][j]>0 && map[i][j+1]>0 && map[i][j]>=0)
                            map[i][j] = map[i+1][j]+map[i][j+1];
                        else
                            map[i][j] = max(map[i+1][j], map[i][j+1]);
                return map[start_x][start_y];
            }
            // 目标点在左下角，出发点在右上角
            else
            {
                for (int i=end_x-1; i>=start_x; i--)
                    if (map[i][end_y] == -1)
                        break;
                    else
                        map[i][end_y] = 1;
                for (int i=end_y-1; i<=start_y; i++)
                    if (map[end_x][i] == -1)
                        break;
                    else
                        map[end_x][i] = 1;

                for (int i=end_x-1; i>=start_x; i--)
                    for (int j = end_y-1; j<=start_y; j++)
                        if (map[i+1][j]>0 && map[i][j+1]>0 && map[i][j]>=0)
                            map[i][j] = map[i+1][j]+map[i][j+1];
                        else
                            map[i][j] = max(map[i+1][j], map[i][j+1]);
                return map[start_x][start_y];                        
            }
        else
            // 目标点在右上角，出发点在左下角
            if (start_y < end_y)
            {
                for (int i=end_x-1; i<=start_x; i++)
                    if (map[i][end_y] == -1)
                        break;
                    else
                        map[i][end_y] = 1;
                for (int i=end_y-1; i>=start_y; i--)
                    if (map[end_x][i] == -1)
                        break;
                    else
                        map[end_x][i] = 1;

                for (int i=end_x-1; i<=start_x; i++)
                    for (int j = end_y-1; j>=start_y; j--)
                        if (map[i+1][j]>0 && map[i][j+1]>0 && map[i][j]>=0)
                            map[i][j] = map[i+1][j]+map[i][j+1];
                        else
                            map[i][j] = max(map[i+1][j], map[i][j+1]);
                return map[start_x][start_y];
            }
            // 目标点在左上角，出发点在右下角
            else
            {
                // 和目标点在一条轴上的点只有一只走法
                for (int i=end_x-1; i<=start_x; i++)
                    if (map[i][end_y] == -1)
                        break;
                    else
                        map[i][end_y] = 1;
                // 同理
                for (int i=end_y-1; i<=start_y; i++)
                    if (map[end_x][i] == -1)
                        break;
                    else
                        map[end_x][i] = 1;
                // 倒推回去，一个点的走法数，等于它可以走到的点的走法数之和
                for (int i=end_x-1; i<=start_x; i--)
                    for (int j = end_y-1; j<=start_y; j++)
                        if (map[i+1][j]>0 && map[i][j+1]>0 && map[i][j]>=0)
                            map[i][j] = map[i+1][j]+map[i][j+1];
                        else
                            map[i][j] = max(map[i+1][j], map[i][j+1]);
                return map[start_x][start_y];
            }
    }
};

/*
解题思路：
动态规划的题，但是这道题动态规划却不是难点，是四种不同的情况

动态规划的题，主要还是建表，求子解。
再倒推回去，在子解中求解。
*/