Intereting Posts
Определение сложностей заданных кодов Среднее время выполнения Почему программы, написанные на Ассамблее чаще всего? Неверное чтение / запись иногда создает ошибку сегментации, а иногда не Как написать программу на C, чтобы проверить, находится ли точка внутри квадрата заданных конечных точек одной из ее диагональных Как отличить sockaddr_storage и не нарушать правила строгого сглаживания Функция для вычисления контрольной суммы CRC16 Отправка сигнала в stream из аннуитетного стека процессов и протоколирования не происходит Как все элементы массива инициализируются до нуля и первого элемента до 1 в c Передача struct в GPU с помощью OpenCL, который содержит массив поплавков MSP430G2553 Интервалы таймера Почему я могу вызвать функцию через указатель со слишком большим количеством аргументов? Любые ссылки на анализ динамического кода? Функция, использующая локальную статическую переменную thread safe / reentrant Как изменить файл DTB ядра

расположение маршрута в поле типа 2-мерного массива

МОЙ КОД:

#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); } 

ОПИСАНИЕ ПРОБЛЕМЫ : Существует grid, через которую движется робот. Робот движется в три направления. Направления направлены вниз и по диагонали вниз. Программа состоит в том, чтобы найти путь робота, чтобы добраться до места назначения от источника, который находится сверху слева от матрицы.

ЧТО Я ОЖИДАЮ:

Мой код печатает все пути для робота в трех направлениях … если я блокирую любую ячейку матрицы, то как будут изменения в пути … и как печатать путь?

Plz .. помогите мне сделать это …

как это

 #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); } 

Ваш вход немного неясен, но в основном вы пытаетесь сделать что-то вроде этого

 #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

Для этой проблемы существует простое математическое наблюдение, позволяющее избежать алгоритма динамического программирования. Вот обзор, чтобы описать процесс, который поможет вам написать код самостоятельно.

Сначала имеет матрицу 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 * см. 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 после (0,1) и включив в себя нули.

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

Не используйте строку для записи пути. Вместо этого используйте массив направлений, сделанных каждым шагом. Если вы используете массив символов, вы можете использовать

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

Заметим, что если matrix имеет N × N ячеек, то максимальная длина пути равна 2 N -2. Длина полного пути изменяется от N -1 (прямой диагональный путь) до 2 N -2 (вдоль двух ребер матрицы).

Вместо того, чтобы найти полный путь, разделите его на отдельные шаги. Функция stepping выполняет один шаг, вызывая себя рекурсивно, пока текущий путь не заблокирован, или прогулка не достигнет нужной ячейки.

В псевдокоде эта функция шага

 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() , путем вывода каждого вызова в качестве узла и каждого рекурсивного вызова в качестве ребра в формате DOT Graphviz.)

Как вы можете видеть, первые пять рекурсивных вызовов находят путь, который перемещается вдоль верхнего правого края матрицы: (0,0)-(1,0)-(2,0)-(2,1)-(2,2) . Второй найденный путь расщепляется от второго шага, давая (0,0)-(1,0)-(2,1)-(2,2) и т. Д. Рассмотрение этого графика и рассмотрение того, какой вызов соответствует тому, какой шаг (ы), в котором путь (ы), должен помочь вам понять, как работают такие рекурсивные поисковые машины.