路线位于像二维arrays的盒子里

我的代码：

#include #include int ch,a[100]; static int i=0,j; int checkIfValidCoordinates(int x, int y, int n, char arr[]){ if(x==a[i]&& y==a[i+1]) { i+=2; return 0; } // arr for this location is invalid // then return 0; return 1; } void path(int u,int v,int n,char arr[],size_t s,size_t p) { ch=1; int x; j=checkIfValidCoordinates(u,v,n,arr); if(j == 0) return; if(u==(n-1)&&v==(n-1)) { p+=snprintf(arr+p,sp,"( %d , %d )",u,v); } else { p+=snprintf(arr+p,sp,"( %d , %d ) - ",u,v); } if(p>=s) { fprintf(stderr,"Small path\n"); exit(1); } if(u==n-1&&v==n-1) { printf("%s\n",arr); } else { { if(u<n-1) { path(u+1,v,n,arr,s,p); } if(v<n-1) { path(u,v+1,n,arr,s,p); } if(u<n-1&&v<n-1) { path(u+1,v+1,n,arr,s,p); } } } } void main() { char arr[1000]; int size; printf("Enter the size of the grid"); scanf("%d",&size); if(size<=0) { printf("\nInvalid Input"); exit(1); } printf("\nEnter the grid points that are offsets"); here1: scanf("%d %d",&a[i],&a[i+1]); if(a[i]==-1&&a[i+1]==-1) { goto here; } else { i+=2; goto here1; } here: printf("\nThe paths for the robot are\n"); i=0; path(0,0,size,arr,sizeof arr,0); } 

问题描述：机器人正在移动一个网格。机器人正在向三个方向移动。方向是向下和对角向下。程序是找到机器人从顶部到达目的地的路径矩阵左边给出。

我期待的是什么：

我的代码在三个方向上打印机器人的所有路径…如果我阻止矩阵的任何单元格，那么路径中的变化将如何…以及如何打印路径？

Plz ..帮我做这个……

Answer 1

像这样

 #include  #include  typedef struct point { int r, c; } Point; void search_path(Point p, int n, char (*blocks)[n], Point *path, size_t path_len){ if(pr == n || pc == n || blocks[pr][pc]) return;//invalid point path[path_len++] = p;//add point to path if(pr == n-1 && pc == n-1){//goal! print path for(size_t i = 0; i < path_len; ++i){ if(i) putchar('-'); printf("( %d , %d )", path[i].r, path[i].c); } puts(""); return; } search_path((Point){ pr +1, pc }, n, blocks, path, path_len);//down search_path((Point){ pr , pc +1 }, n, blocks, path, path_len);//right search_path((Point){ pr +1, pc +1 }, n, blocks, path, path_len);//diagonally down } int main(void){ int size = 0; printf("Enter the size of the grid\n"); scanf("%d", &size); if(size <= 0){ printf("\nInvalid Input\n"); exit(1); } Point *path = malloc((size * 2 - 1) * sizeof(*path));//check omitted char (*blocks)[size] = calloc(size, sizeof(*blocks)); printf("\nEnter the grid points that are offsets\n"); Point offset; while(scanf("%d %d", &offset.r, &offset.c)==2){ if(offset.r == -1 && offset.c == -1) break; blocks[offset.r][offset.c] = 1; } printf("\nThe paths for the robot are\n"); search_path((Point){0, 0}, size, blocks, path, 0); free(blocks); free(path); } 

Answer 2

您的输入有点不清楚，但基本上您正在尝试做这样的事情

 #include #include int ch,a[100]; static int i=0; int checkIfValidCoordinates(int x, int y, int n, char arr[]){ if(x<0 || y<0 || x>n-1 || y>n-1) return 0; // arr for this location is invalid // then return 0; return 1; } void path(int u,int v,int n,char arr[],size_t s,size_t p) { if(checkIfValidCoordinates() == 0) return; if(u==(n-1)&&v==(n-1)) { p+=snprintf(arr+p,sp,"( %d , %d )",u,v); } else { p+=snprintf(arr+p,sp,"( %d , %d ) - ",u,v); } if(p>=s) { fprintf(stderr,"Small path\n"); exit(1); } if(u==n-1&&v==n-1) { printf("%s\n",arr); } else { if(u 

只需为checkIfValidCoordinates函数添加条件

Answer 3

对这个问题有一个简单的数学观察，避免了动态编程算法。 以下是描述帮助您自己编写代码的过程的观察结果。

首先有一个NxN矩阵M ，其中所有条目都是-1 。 假设N = 3 。 矩阵将是：

 -1 -1 -1 -1 -1 -1 -1 -1 -1 

接下来用0填充偏移正方形。 设（1,1）为偏移平方，因此我们将其标记为零。

 -1 -1 -1 -1 0 -1 -1 -1 -1 

将顶行标记为全1s ，最左侧列标记为1s *， 请参见下面的边框 。

  1 1 1 1 0 -1 1 -1 -1 

这是美丽的数学部分，通知，在顶行或最左列的任何给定方格上，该方块的路径数是上，左上，左前一个方格的总和，例如M[i][j] = M[i-1][j] + M[i-1][j-1] + M[i][j-1] 。 遍历矩阵并为每个-1平方计算该平方的总和，直到达到底部。 如果一个正方形为零，请忽略它并继续前进！

 1 1 1 1 0 2 1 2 4 

注意每个方格是上，左上和左方的总和。 最右下方的正方形是从左上角到右下角的可能路径的答案。

边缘情况：当您将方块标记为偏移0s ，如果偏移方块恰好位于顶行或最左列 ，请标记以全零结尾的相应方向。 例如，令（0,1）为N = 3的偏移量，将（0,1）和包括之后的第0行的所有正方形标记为零。

 1 0 0 1 -1 -1 1 -1 -1 

Answer 4

不要使用字符串来记录路径。 相反，使用每一步采取的一系列方向。 如果使用char数组，则可以使用

 #define RIGHT 1 #define DOWN 2 /* Down-right is DOWN|RIGHT == RIGHT|DOWN */ 

注意，如果矩阵具有N × N单元，则路径的最大长度为2 N -2。 完整路径的长度从N -1（直的对角线路径）到2 N -2（沿着矩阵的两个边缘）变化。

而不是找到完整的路径，将其拆分为单独的步骤。 步进function需要一步，递归调用自身，直到当前路径被阻塞，或者步行到达所需的单元格。

在伪代码中，此步骤function是

 Define RIGHT = 1 Define DOWN = 2 Function Step(n, row, col, i, map[], path[]): # n is the number of rows and columns in the map # row is the current row # col is the current column # i is the number of steps already taken # map[n*row+col] is nonzero if the cell is blocked # path[i] is the direction for the next step # If we arrived at a blocked cell, this path # will not lead to target. If (map[n*row+col] != 0): Return End If # When we reach the target, we print the path. If (row == n-1) and (col == n-1): x = 0 y = 0 Print "(x,y)" For (j = 0; j < i; j++): If (path[j] & RIGHT) x++ If (path[j] & DOWN) y++ Print "-(x,y)" End For Print newline Return End If # If we can step right, we try that. If (col < size - 1): path[i] = RIGHT Step(n, row, col+1, i+1, map, path) End If # If we can step diagonally down, we try that. If (col < size - 1) and (row < size - 1): path[i] = DOWN | RIGHT Step(n, row+1, col+1, i+1, map, path) End If # If we can step down, we try that. If (row < size - 1): path[i] = DOWN Step(n, row+1, col, i+1, map, path) End If Return End Function 

因为Step()函数是递归的，所以在每一步我们将当前路径分成最多三个不同的子路径，具体取决于我们采取的步骤。 （因为路径最多2 N -2步长，我们的最大递归深度也是2 N -2。这意味着我们不需要担心由于递归调用而耗尽堆栈空间。）

如果我们绘制一个图形，我们用K: (X, Y)标记每个节点，其中K是递归调用的编号（1表示第一个，2表示秒，依此类推）， X和Y是列和行分别在Step()调用的矩阵中，我们得到以下结果：

（该图是使用实现上述伪代码的C代码生成的，并且每个Step()调用都会增加一个全局计数器，方法是将每个调用作为节点输出，并将每个递归调用作为边缘，以Graphviz DOT格式输出。）

如您所见，前五个递归调用找到沿矩阵右上边缘传播的路径： (0,0)-(1,0)-(2,0)-(2,1)-(2,2) 。 发现第二条路径与第二条路径分开，产生(0,0)-(1,0)-(2,1)-(2,2) ，依此类推。 检查该图，并考虑哪个调用对应于路径中的哪个步骤，应该有助于您了解这些递归路径查找器的工作原理。