Created
April 4, 2014 18:56
-
-
Save halit/9981007 to your computer and use it in GitHub Desktop.
matrix traverse problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// ===================================================================================== | |
// | |
// 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