Skip to content

Instantly share code, notes, and snippets.

@halit
Created April 4, 2014 18:56
Show Gist options
  • Save halit/9981007 to your computer and use it in GitHub Desktop.
Save halit/9981007 to your computer and use it in GitHub Desktop.
matrix traverse problem
// =====================================================================================
//
// Filename: path.c
//
// Description:
//
// Version: 1.0
// Created: 03/26/2014 09:31:02 PM
// Revision: none
// Compiler: gcc
//
// Author: Halit Alptekin (), [email protected]
// Organization:
//
// =====================================================================================
#include <stdio.h>
#include <stdlib.h>
int** init_matrix(unsigned int row, unsigned int col){
int i, j;
int** matrix = (int**)malloc(sizeof(int)*row);
for(i=0;i<row;i++) matrix[i] = (int*)malloc(sizeof(int)*col);
for(i=0;i<row;i++) for(j=0;j<col;j++) scanf("%d", &matrix[i][j]);
return matrix;
}
int* init_path_matrix(unsigned int size){
return (int*)malloc(sizeof(int)*size);
}
void destroy_path_matrix(int* matrix){
free(matrix);
}
void destroy_matrix(int** matrix, unsigned int row){
int i;
for(i=0;i<row;i++) free(matrix[i]);
free(matrix);
}
void print_matrix(int** matrix, unsigned int row, unsigned int col){
int i, j;
for(i=0;i<row;i++){
for(j=0;j<col;j++) printf("%3d ", matrix[i][j]);
printf("\n");
}
}
void print_path(int* path, unsigned int size){
int i;
for(i=0;i<size-1;i++) printf("%d->", path[i]);
printf("%d\n", path[size-1]);
}
void path_matrix(int** matrix, int* path, unsigned int pi, unsigned int i, unsigned int j, unsigned int row, unsigned int col){
if((i == row-1) && (j == col-1)){
path[pi] = matrix[i][j];
print_path(path, row+col-1);
return;
}
if((i >= row) || (j >= col)) return;
path[pi] = matrix[i][j];
path_matrix(matrix, path, pi+1, i+1, j , row, col);
path_matrix(matrix, path, pi+1, i, j+1, row, col);
}
int main(int argc, const char *argv[]){
unsigned int row = 3;
unsigned int col = 3;
int** matrix = init_matrix(row, col);
int* path_array = init_path_matrix(row+col-1);
print_matrix(matrix, row, col);
path_matrix(matrix, path_array, 0, 0, 0, row, col);
destroy_matrix(matrix, row);
destroy_path_matrix(path_array);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment