problem in using DFS for solving a shortest path in maze in C

Question

I'm working on a maze-solving program using a Depth-First Search (DFS) algorithm in C. The program is designed to find the shortest path from the start ('S') to the end ('E') in a maze represented by a 2D grid. The goal is to prioritize going right, then left, then up, and finally down. However, I'm encountering an issue where the algorithm seems to prioritize going down even after changing the direction vector.

#include <stdio.h>

char grid[15][15];
int visited[15][15];
int x, y;
int moveX[4] = {1, -1, 0, 0};
int moveY[4] = {0, 0, 1, -1};
int length = 0;
int startX, startY, endX, endY;
int minimum = 2147483647;

/*
int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {1, -1, 0, 0};
int moveX[4] = {1, -1, 0, 0};
int moveY[4] = {0, 0, 1, -1};
*/

void depthfirstsearch(int currX, int currY) {
    visited[currX][currY] = 1;
    // kalo udh ketemu jarak terpendek recur dari sini
    if (currX == endX && currY == endY) {
        if (length < minimum) {
            minimum = length;
            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    if (visited[i][j] && grid[i][j] != 'S' && grid[i][j] != 'E') {
                        grid[i][j] = 'x';
                    } else if (grid[i][j] == 'x') {
                        grid[i][j] = '.'; 
                    }
                }
            }
        }
        visited[currX][currY] = 0;  
        return;
    }


    for(int i = 0; i < 4; i++){
        int newX = currX + moveX[i];
        int newY = currY + moveY[i];


        if(newX >= 0 && newY >= 0 && newX < x && newY < y && grid[newX][newY] != '#' && !visited[newX][newY]){
            length++;
            depthfirstsearch(newX, newY);  
            length--;  // Backtrack buat nyari jarak terpendek, klo ngak, bakalan malah lebih
        }
    }

    visited[currX][currY] = 0;  // Backtracking klo misal lebih
}


int main() {
    scanf("%d %d", &y, &x);
        for(int i = 0; i < x; i++){
            scanf("%s", grid[i]);
        }


    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            if(grid[i][j] == 'S'){
                startX = i;
                startY = j;
            }
            else if(grid[i][j] == 'E'){
                endX = i;
                endY = j;
            }
        }
    }

    length = 0;
    depthfirstsearch(startX, startY);
    if(minimum == 2147483647){
        printf("tujuan tidak ditemukan\n");
    } 
    else{
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                printf("%c", grid[i][j]);
            }
            printf("\n");
        }
    }
    
    return 0;
}

The issue I'm facing is that the algorithm seems to prioritize moving downward even after changing the direction vector. For example, when the input is a 15x13 maze:

15 13
###############
#S...........##
#............##
#...........E##
###############
###############
###############
###############
###############
###############
###############
###############
###############

the output prioritze downward first rather than right

###############
#S...........##
#x...........##
#xxxxxxxxxxxE##
###############
###############
###############
###############
###############
###############
###############
###############
###############

Which is wrong but when i input

5 5
#E..#
#...#
#...#
##...
####S

the output is supposed to be correct because i prioriotze right left up down

#Exx#
#..x#
#..x#
##.xx
####S

which is the supposed answer

but the weird thing is when i switch the condition of the lenght and minimum from

if (length < minimum)

to

if (length <= minimum)

it changes, and the 15 13 becomes

###############
#Sxxxxxxxxxxx##
#...........x##
#...........E##
###############
###############
###############
###############
###############
###############
###############
###############
###############

but the 6 5 becomes

####S
#E..#
#x..#
#xx.#
##xxx
####S

When I switch the condition from if (length < minimum) to if (length <= minimum), the outputs change inconsistently.

Any suggestions on how to fix this issue and ensure consistent prioritization of directions in my maze-solving DFS algorithm?

Answer 1

Change the start of main to

scanf("%d %d", &y, &x);
for(int i = 0; i < x; i++){
    scanf("%s", grid[i]);
}

If you had printed out the grid for the "nothing found" cases, you could have noticed that part of the board is missing.

The customary way of addressing a 2D array is array[y][x]. Your input data is consistent with that, your usage is not.

Verdict: you seem have reversed the dimensions in places.