I was recently assigned a problem, which boils down to finding the longest path in a given matrix, where two cells are adjacent iff the neighboring value is less than the present cell. I've been tearing my hair out trying to figure it out, so I would be extremely grateful for any help. However, as I said, this is a homework assignment, so suggestions and hints are very welcome (but try not to make it too easy for me).
Here's the latest version of my code:
#include <stdio.h>
int isValid(int i, int j, int rows, int cols) {
if (i < 0 || i >= rows || j < 0 || j >= cols)
return 0;
return 1;
}
void printpath(int path[1000][2]) {
int i = 0;
while (path[i][0] != -1) {
printf("(%d, %d) ", path[i][0], path[i][1]);
i++;
}
}
void print_array_path(int path[1000][2], int array[100][100]) {
int i = 0;
while (path[i][0] != -1) {
printf("%d -> ", array[path[i][0]][path[i][1]]);
i++;
}
}
int path_length(int path[1000][2]) {
int i = 0, s = 0;
while ( path[i][0] != -1) {
s++;
i++;
}
return s-1;
}
void add_path(int path[1000][2], int u, int v) {
int i = 0;
while (path[i][0] != -1) {
i++;
}
path[i][0] = u; // row
path[i][1] = v; // column
}
int last_i(int path[1000][2], int s) {
int v;
v = path[s][0];
//path[i-2][0] = -1;
return v;
}
int last_j(int path[1000][2], int s) {
int u;
u = path[s][1];
//path[i-2][1] = -1;
return u;
}
int c1[4] = {1, 0, -1, 0};
int c2[4] = {0, 1, 0, -1};
int dfs(int visited[100][100], int array[100][100], int i, int j, int rows, int cols, int path[1000][2], int length) {
// 1. Take the current visited, along with the previous vertex, to create a unique
// list of visited vertices.
// 2. For every direction, check if it is valid. If valid, do dfs(visited, current, choice)
// 3. If all four directions are checked, with no valid choice, report the solution.
int s;
for (s=0; s<4; s++) {
if ( isValid(i+c1[s], j+c2[s], rows, cols) && !(visited[i+c1[s]][j+c2[s]]) && (array[i][j] < array[i+c1[s]][j+c2[s]]) ) {
// TODO visited.add(current)
visited[i][j] = 1;
add_path(path, i+c1[s], j+c2[s]);
//printf("%d -> ", array[i+c1[s]][j+c2[s]]);
//printpath(path);
length += 1;
dfs( visited, array, i+c1[s], j+c2[s], rows, cols, path, length);
} else if (s==3) {
//visited[i+c1[s]][j+c2[s]] = 0;
//printf("end at %d, %d\n", i, j);
if ( (last_i(path, i) == i) && (last_i(path, j) == j) ){
printf("%d ", length);
print_array_path(path, array);
printf("\n");
continue;
}
length -= 1;
dfs(visited, array, last_i(path, i-1), last_j(path, i-1), rows, cols, path, length);
return path[i][0];
}
}
}
int main() {
int array[100][100];
int rows, columns;
scanf("%d", &rows);
scanf("%d", &columns);
int i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
scanf("%d", &array[i][j]);
}
}
for (i = 0; i < rows; i++) {
for (j = 0; j < columns; j++) {
printf("%d ", array[i][j]);
}
printf("\n");
}
int visited[100][100];
for (i=0; i<rows; i++) {
for (j=0; j<columns; j++) {
visited[i][j] = 0;
}
}
int path[1000][2];
for (i=0; i<1000; i++) {
for (j=0; j<2; j++) {
path[i][j] = -1;
}
}
path[0][1] = 0;
path[0][0] = 0;
int length = 0;
dfs(visited, array, 0, 0, rows, columns, path, length);
}
Basically, it first collects an inputted matrix, and starts at the first cell (once I get the whole thing working, it would move through every cell), calls a search function, checks to see if a neighboring cell is valid, then calls the search again. If all four directions have been checked, it backtracks. The current path is tracking in a list path. My problem seems to mostly be in the backtracking part. However, I'm not sure how to move forward. This code barely compiles at the moment, as I've been trying so many different things. At this point, I'd like to catch my breath and really understand what I'm trying to do.
Earlier on, I tried generating an adjacency list, and constructing paths from that, but the backtracking option seemed more promising. A typical input looks like this:
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
To express a 5x5 matrix. The expected output would be 25 (25->24-> ... 2->1). Please let me know if any other info would be helpful. Any advice / tips would be greatly appreciated! Thanks.
EDIT: The original problem was reversed (i.e two cells are adj iff the neighbor has a strictly lower value. The two problems are equivalent, right?)
EDIT 2: I made some changes to the code, and I think I'm a bit closer. It now gives this output:
3 1 -> 16 -> 17 -> 24 -> 25 ->
3 1 -> 16 -> 17 -> 24 -> 25 ->
4 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 ->
9 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 ->
10 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 ->
17 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 ->
20 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 ->
21 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 ->
21 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 ->
19 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
19 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
13 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
12 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
11 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
9 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
7 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
8 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
7 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
5 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
4 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
2 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
1 1 -> 16 -> 17 -> 24 -> 25 -> 18 -> 25 -> 19 -> 20 -> 21 -> 22 -> 25 -> 23 -> 25 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 23 -> 13 -> 14 -> 23 -> 15 -> 25 ->
I replaced the above code to reflect those changes. It seems very close, but not quite the right answer, namely, the path seems to be found but the lengths are not correct.
The main problem of the current code is trackback.
It is necessary to return the environment after executing the function.
Specific modification example:
#include <stdio.h>
#include <stdbool.h>
#define MAX_LEN 1000
#define SIZE 100
#define EOP -1 //End Of Path
typedef struct pos {
int r, c;//rows, columns
} Pos;
Pos EPOS = { EOP, EOP};
bool isValidPos(Pos pos, int rows, int cols) {
return 0 <= pos.r && pos.r < rows && 0 <= pos.c && pos.c < cols;
}
bool isVisited(Pos pos, bool visited[SIZE][SIZE]){
return visited[pos.r][pos.c];
}
/* unused
void printPos(Pos pos){
printf("(%d, %d)", pos.r, pos.c);
}
void printpath(Pos path[]){
while(path->r != EOP)
printPos(*path++);
}
int path_length(Pos path[]) {
int i = 0;
while((path++)->r != EOP)
++i;
return i;
}
void add_path(Pos path[], Pos pos) {
while (path->r != EOP)
++path;
*path = pos;
path[1] = EPOS;
}
*/
int valueOf(Pos pos, int array[SIZE][SIZE]){
return array[pos.r][pos.c];
}
void print_path(Pos path[], int array[SIZE][SIZE]){
while(path->r != EOP)
printf("%d -> ", valueOf(*path++, array));
}
const Pos rpos[] = {{1,0},{0,1},{-1,0},{0,-1}};//relative position
void dfs(bool visited[SIZE][SIZE], int array[SIZE][SIZE], Pos pos, int rows, int cols, Pos path[], int length){
visited[pos.r][pos.c] = true;
int value = valueOf(pos, array);
bool CantAddPath = true;
for (int s = 0; s < sizeof(rpos)/sizeof(*rpos); s++){
Pos movePos = { .r = pos.r + rpos[s].r, .c = pos.c + rpos[s].c};
if(!isValidPos(movePos, rows, cols) || isVisited(movePos, visited) || value >= valueOf(movePos, array))
continue;
CantAddPath = false;
path[length++] = pos;//add_path(path, pos);length++;
dfs(visited, array, movePos, rows, cols, path, length);
path[--length] = EPOS;
}
if(CantAddPath){
printf("%d ", length+1);//+1: current (last) postion
print_path(path, array);
printf("%d\n", value);//value of current (last) position
}
visited[pos.r][pos.c] = false;
}
int main(void) {
int array[SIZE][SIZE];
int rows, columns;
scanf("%d", &rows);
scanf("%d", &columns);
int i, j;
for(i = 0; i < rows; i++)
for(j = 0; j < columns; j++)
scanf("%d", &array[i][j]);
for(i = 0; i < rows; i++){
for(j = 0; j < columns; j++)
printf("%2d ", array[i][j]);
printf("\n");
}
bool visited[SIZE][SIZE] = {{ false }};
Pos path[MAX_LEN];
for (i = 0; i < MAX_LEN; i++){
path[i] = EPOS;
}
Pos start = { 0, 0 };
//path[0] = start;//Mismatch with `int length = 0;`
int length = 0;
dfs(visited, array, start, rows, columns, path, length);
}