注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex63 Unique Paths II  

2015-05-18 21:55:25|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
上一题ex62的升级版,这里用障碍物

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

开始写了一个递归,直接全部遍历了一遍,貌似复杂度太高,oj不让过,如下

nt traverse(int **matrix,int m,int n,int i,int j,int direction, int *treturnSize)
{
if (i == (m-2) &&j == (n-2))
{
treturnSize[0]++;
return 0;//正常退出
}
else
{
// 否则的话有两种遍历方式 direction 0 是向右 1 是向左
int index1, index2;
index1 = i + 1;
index2 = j + 1;
if ((matrix[index1][j] == 1) && (matrix[i][index2] == 1))
{
//没有路了,被堵住了
return -1;
}
if (matrix[index1][j] != 1)
{
traverse(matrix, m, n, index1, j, direction, treturnSize);
}
if (matrix[i][index2] != 1)
{
traverse(matrix, m, n, i, index2, direction, treturnSize);
}
return 1;
}
}

int uniquePathsWithObstacles1(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {
//递归的方式搜索路径,复杂度太高了
int m = obstacleGridRowSize;
int n = obstacleGridColSize;
int i, j;
int newM = m + 2;
int newN = n + 2;
int **matrix = (int**)malloc((m+2)*sizeof(int*));
for (i = 0; i < m+2; i++)
{
matrix[i] = (int*)malloc((n+2)*sizeof(int));
for (j = 0; j < n+2; j++)
{
matrix[i][j] = 1;
}
}

for (i = 1; i < m + 1; i++)
{
for (j =1 ; j < n + 1; j++)
{
matrix[i][j] = obstacleGrid[i-1][j-1];
}
}
//show(matrix, m+2, n+2);
int returnSize = 0;
int direction,startX =1,startY =1;
direction= 0;
int result = traverse(matrix, newM, newN, startX, startY, direction, &returnSize);

// free
for (i = 0; i < newM; i++)
free(matrix[i]);
free(matrix);
matrix = NULL;

return returnSize;
}

后来也是用网上说的矩阵滚动的方法,如下

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) {

int m = obstacleGridRowSize;
int n = obstacleGridColSize;
int i, j;
int **matrix = (int**)malloc(m*sizeof(int*));
for (i = 0; i < m; i++)
{
matrix[i] = (int*)malloc(n*sizeof(int));
}
//if (obstacleGrid[0][0] == 1)
//{
// matrix[0][0] = 0;
//}
//else
//{
// matrix[0][0] = 1;
//}
matrix[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
for (i = 1; i < m; i++)
{
//第一列赋值为1
matrix[i][0] = obstacleGrid[i][0] == 1 ? 0 : matrix[i - 1][0];
//if (obstacleGrid[i][0] == 1)
//{
// matrix[i][0] = 0;
//}
//
//else
//{
// matrix[i][0] = matrix[i-1][0];
//}
}

for (i = 1; i < n; i++)
{
//第一行赋值为1
matrix[0][i] = obstacleGrid[0][i] == 1 ? 0 : matrix[0][i - 1];
//if (obstacleGrid[0][i] == 1)
//{
// matrix[0][i] = 0;
//}
//else
//{
// matrix[0][i] = matrix[0][i-1];
//}
}


for (i = 1; i < m; i++)
{
for (j = 1; j < n; j++)
{
//这里开一矩阵,计算从起始点到当前位置步骤
//相当于可以有上面的两个点走到该点
matrix[i][j] = obstacleGrid[i][j] == 1 ? 0 : matrix[i - 1][j] + matrix[i][j - 1];


//if (obstacleGrid[i][j] == 1)
//{
// matrix[i][j] = 0;
//}
//else
//{
// matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
//}
}
}

int result = matrix[m - 1][n - 1];
// free
for (i = 0; i < m; i++)
free(matrix[i]);
free(matrix);
matrix = NULL;

return result;
}


参考
http://www.cnblogs.com/remlostime/archive/2012/11/15/2772282.html
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017