在二维网格 grid 上,有 4 种类型的方格:
1 表示起始方格。且只有一个起始方格。
2 表示结束方格,且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。
返回在四个方向(上、下、左、右)上行走时,从起始方格到结束方格的不同路径的数目。 每一个无障碍方格都要通过一次,但是一条路径中不能重复通过同一个方格。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
int position[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int **grid_temp = NULL;
int x1 = 0;
int x2 = 0;
int ret = 0;
int **used = NULL;
int num = 0;
void backtrack(int index, int x, int y, int total)
{
if(index == total)
{
for(int i = 0; i < 4; i++)
{
if((x+position[i][0] >= 0 && x+position[i][0] < x1) //上下左右寻找2
&& (y+position[i][1] >= 0 && y+position[i][1] < x2)
&& grid_temp[x+position[i][0]][y+position[i][1]] == 2)
{
ret++;
return;
}
}
}
for(int i = 0; i < 4; i++)
{
if((x+position[i][0] >= 0 && x+position[i][0] < x1) //上下左右寻找0
&& (y+position[i][1] >= 0 && y+position[i][1] < x2)
&& grid_temp[x+position[i][0]][y+position[i][1]] == 0
&& used[x+position[i][0]][y+position[i][1]] == 0) //一条路径中不能重复通过同一个方格
{
used[x+position[i][0]][y+position[i][1]] = 1;
backtrack(index+1, x+position[i][0], y+position[i][1], total);
used[x+position[i][0]][y+position[i][1]] = 0;
}
}
}
int uniquePathsIII(int** grid, int gridSize, int* gridColSize){
ret = 0;
x1 = gridSize;
x2 = gridColSize[0];
grid_temp = grid;
num = x1 * x2;
used = (int **)malloc(sizeof(int*) * x1);
for(int i = 0; i < x1; i++)
{
used[i] = (int*)malloc(sizeof(int) * x2);
memset(used[i], 0, sizeof(int) * x2);
}
int x, y,obstacle = 0;
for(int i = 0; i < x1; i++)
{
for(int j = 0; j < x2; j++)
{
if(grid[i][j] == 1) //寻找起点
{
x = i;
y = j;
}
else if(grid[i][j] == -1) //寻找障碍的个数
{
obstacle++;
}
}
}
backtrack(0, x, y,num - obstacle - 2);
for(int i = 0; i < x1; i++)
{
free(used[i]);
}
free(used);
return ret;
}
思路·:回溯算法