C++ 笔试题 之基础 45 机器人走方格II

题目描述

有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。注意这次的网格中有些障碍点是不能走的。

给定一个int[][] map(C++ 中为vector >),表示网格图，若map[i][j]为1则说明该点不是障碍点，否则则为障碍。另外给定int x,int y，表示网格的大小。请返回机器人从(0,0)走到(x - 1,y - 1)的走法数，为了防止溢出，请将结果Mod 1000000007。保证x和y均小于等于50

经典动态规划，

建立规划矩阵f

遍历所有情况，生成f举证就可以，

对map的处理：不能走这个点，说明这个点的可能路径走法==0，经过不能走的点写成0就可以了

总结一下就是：

1. 不能走，就是方法数==0
2. 起点，1种走法
3. 上边沿：只能从左边来
4. 左边沿：只能从上边来
5. 其他点：左边+上边
6. 
   
      int countWays(vector<vector<int> > map, int x, int y) {
           vector<vector<int> > f(x,vector<int>(y,0));
           for(int i=0;i<x;i++)
               for(int j=0;j<y;j++)
               {
                 if(map[i][j] != 1)f[i][j] = 0; // 不能走，就是方法数==0
                 else if(i==0 && j==0)f[i][j] = 1; // 起点，1种走法
                   else if(i==0 && j!=0)f[i][j] = f[i][j-1]; // 上边沿：只能从左边来
                   else if(i!=0 && j==0)f[i][j] = f[i-1][j]; // 左边沿：只能从上边来
                   else f[i][j] = (f[i-1][j]+f[i][j-1]) % 1000000007;其他：左边+上边
               }
            return f[x-1][y-1];
       }

方法二：