1.1 题目要求 一个N x N的矩阵代表了一个迷宫，迷宫中每个房间由以下三种数字的一种来表示： 0 代表房间安全，是可以通过的。 1 代表房间中有奖励物品，玩家可以拿到奖励并通过房间。 -1 代表房间中有障碍，玩家不能通过房间。 你的任务是在遵守下列规则的情况下，尽可能多的拿到奖励： 玩家从起始位置 (0, 0) 出发，到达终点(N-1, N-1) ，只能向下或向右走，并且只能穿越有效的房间（即只可以穿过值为0或者1的房间）；当到达 (N-1, N-1) 后，完成走动过程；当你经过一个房间且这个房间有奖励时，拿到奖励后这个房间会变成空的（值变为0）；如果在(0, 0)和(N-1, N-1)之间不存在一条可经过的路径，则没有奖励能被拿到。
思路：DP + DFS 先找到能获得最大的奖励，再通过DFS从后往前找路径
#include<stdio.h> #include<stdlib.h> #define LEN 4 int matrix[LEN][LEN] = { 0, 1, 1, -1, 1, 0, -1, 0, 1, 1, 0, 1, -1, 0, 1, 0}; int DP[LEN + 1][LEN + 1] = {0}; int Route[LEN + 1][LEN + 1] = {0}; void PrintNums(int (*matrix)[LEN]){ for(int i = 0; i < LEN; i++){ for(int j = 0; j < LEN; j++){ printf("%d ", matrix[i][j]); } printf("\n"); } } void PrintDP(int (*matrix)[LEN + 1]){ for(int i = 1; i < LEN + 1; i++){ for(int j = 1; j < LEN + 1; j++){ printf("%d ", matrix[i][j]); } printf("\n"); } } int Max(int num1, int num2){ return num1>=num2?num1:num2; } int FindMaxValue(int (*matrix)[LEN]){ int MaxValue = 0; for(int i = 1; i < LEN + 1; i++){ for(int j = 1; j < LEN + 1; j++){ if(matrix[i-1][j-1] != -1){ MaxValue = Max(DP[i-1][j], DP[i][j-1]); DP[i][j] = MaxValue + matrix[i-1][j-1]; } } } MaxValue = DP[LEN][LEN]; return MaxValue; } void DFS(int i, int j){ Route[i][j] = 1;//标记当前已经走过的路径 printf("%d %d\n",i,j); if(i == 1 && j == 1){ return; } if(j >= 2 && (DP[i][j] == DP[i][j-1] || DP[i][j] == DP[i][j-1] + 1)){ DFS(i, j-1);//不加 >=2 会断错误 类似1 -1 1 -2 return;//如果是寻找最大礼物的所有路径则无需加return 可见最后2 } if(i >= 2 && (DP[i][j] == DP[i-1][j] || DP[i][j] == DP[i-1][j] + 1)){ DFS(i-1, j); return; } } void FindRoute(int MaxValue){ int i = LEN; int j = LEN; Route[i][j] = 1; Route[0][0] = 1; while(i != 0 && j != 0) { if(DP[i][j-1] == MaxValue) { Route[i-1][j] = 1; i--; } else if(DP[i][j-1] == MaxValue) { Route[i][j-1] = 1; j--; } else { if(DP[i-1][j] == MaxValue - 1) { Route[i-1][j] = 1; i = i - 1; MaxValue --; } else { Route[i][j-1] = 1; j = j - 1; MaxValue --; } } } } void main(){ //int row = sizeof(matrix)/sizeof(matrix[0]); //int column = sizeof(matrix[0])/sizeof(matrix[0][0]); PrintNums(matrix); printf("获取最大礼物值：%d\n", FindMaxValue(matrix)); //PrintDP(DP); //FindRoute(FindMaxValue(matrix)); printf("DP动态规划后数组值\n"); PrintDP(DP); DFS(LEN,LEN); printf("获取最大礼物值的路线\n"); PrintDP(Route); }实验结果图： 没加return 递归过程会出现左和上两个分支去探测
