这个题因为原链接的图片挂了,不过根据题意,题意是:给一个m*n的矩阵,问有多少条路径可以从(0,0)点到(m-1,n-1)点。
走路的规则是 一步只能从当前点往右或者往下走。
宽度优先搜索。
附上代码:
一次AC。目测代码性能还是不够好。
struct PPoint { int x; int y; }; class Solution { public: bool CheckIn(int x,int y,PPoint *p,int top) { for(int i = 0;i < top;i++) { if(x == p[i].x && y == p[i].y) { return true; } } return false; } int uniquePaths(int m, int n) { int **map = new int*[m]; for(int i = 0;i < m;i++) { map[i] = new int[n]; } for(int i = 0;i < m;i++) { for(int j = 0;j <n ;j++) { map[i][j] = 0; } } map[0][0] = 1; PPoint *p = new PPoint[m+n]; PPoint *p_c = new PPoint[m+n]; int index = 0; p[index].x = 0; p[index++].y = 0; while(true) { int top = 0; for(int i = 0;i < index;i++) { int x = p[i].x; int y = p[i].y; if(x + 1 < m) { map[x+1][y] += map[x][y];</p> <pre><code> if(CheckIn(x+1,y,p_c,top) == false) { p_c[top].x = x+1; p_c[top++].y = y; } } if(y + 1 &lt; n) { map[x][y+1] += map[x][y]; if(CheckIn(x,y+1,p_c,top) == false) { p_c[top].x = x; p_c[top++].y = y+1; } } } if(top == 0) break; index = top; for(int i = 0;i &lt; top;i++) { p[i].x = p_c[i].x; p[i].y = p_c[i].y; } } return map[m-1][n-1]; } </code></pre> <p>};