A full description of The problem is on this website: 10 Kinds of People – Kattis, Kattis

The way I'm going about solving this problem is using recursion and in each call, looking to see if I can move North, South, East and West in a depth search manner.

When I submitted my solution, I got 23/25 cases but it was too slow unfortunately so now I need to try to optimize my code so that it can run quicker. What I think is causing my program to run slow is the fact that I'm resetting the grid each time I'm done trying to find a path for a binary or decimal user.

Unfortunately, this is something I need to do because I insert an asterisk each time I visit a cell so that I know I've been there and I need to restore the map to its original condition because it may be the case that I visit that cell again when trying to find a different path. Any ideas on how to better approach this?

Code:#include <stdio.h> #include <stdlib.h> #define BINARY 0 #define DECIMAL 1 char **initGrid(const int, const int); void findBinOrDecPath(char **, char, int *, int, int, const int, const int, const int, const int); void resetGrid(char **, const int, const int, char); int main() { int numOfRows, numOfColumns, numOfQueries, startingX, startingY, destX, destY, typeOfPath = -1, i; char **grid; scanf("%d %d", &numOfRows, &numOfColumns); grid = initGrid(numOfRows, numOfColumns); scanf(" %d", &numOfQueries); for(i = 0; i < numOfQueries; i++) { scanf("%d %d %d %d", &startingX, &startingY, &destX, &destY); findBinOrDecPath(grid, '0', &typeOfPath, startingX - 1, startingY - 1, destX - 1, destY - 1, numOfRows, numOfColumns); resetGrid(grid, numOfRows, numOfColumns, '0'); if(typeOfPath != 0) { findBinOrDecPath(grid, '1', &typeOfPath, startingX - 1, startingY - 1, destX - 1, destY - 1, numOfRows, numOfColumns); resetGrid(grid, numOfRows, numOfColumns, '1'); if(typeOfPath == 1) { printf("decimal"); } else printf("neither"); } else printf("binary"); typeOfPath = -1; printf("\n"); } free(grid); return 0; } char **initGrid(const int numOfRows, const int numOfColumns) { char **grid; char *data; int i, j; const size_t row_pointers_bytes = numOfRows * sizeof (char *); const size_t row_elements_bytes = numOfColumns * sizeof (char); grid = malloc(row_pointers_bytes + numOfRows * row_elements_bytes); data = (char *)grid + row_pointers_bytes; for(i = 0; i < numOfRows; i++) grid[i] = data + i * numOfColumns; for(i = 0; i < numOfRows; i++) { for(j = 0; j < numOfColumns; j++) { scanf(" %c", &grid[i][j]); } } return grid; } void findBinOrDecPath(char **grid, char typeOfUser, int *typeOfPath, int startingX, int startingY, const int destX, const int destY, const int numOfRows, const int numOfColumns) { if(grid[startingX][startingY] != typeOfUser) { return; } if(startingX == destX && startingY == destY) { if(typeOfUser == '0') { *typeOfPath = BINARY; } else *typeOfPath = DECIMAL; } if(startingX - 1 >= 0 && grid[startingX - 1][startingY] == typeOfUser && grid[startingX - 1][startingY] != '*') { grid[startingX][startingY] = '*'; findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX - 1, startingY, destX, destY, numOfRows, numOfColumns); } if(startingX + 1 < numOfRows && grid[startingX + 1][startingY] == typeOfUser && grid[startingX + 1][startingY] != '*') { grid[startingX][startingY] = '*'; findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX + 1, startingY, destX, destY, numOfRows, numOfColumns); } if(startingY + 1 < numOfColumns && grid[startingX][startingY + 1] == typeOfUser && grid[startingX][startingY + 1] != '*') { grid[startingX][startingY] = '*'; findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX, startingY + 1, destX, destY, numOfRows, numOfColumns); } if(startingY - 1 >= 0 && grid[startingX][startingY - 1] == typeOfUser && grid[startingX][startingY - 1] != '*') { grid[startingX][startingY] = '*'; findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX, startingY - 1, destX, destY, numOfRows, numOfColumns); } } void resetGrid(char **grid, const int numOfRows, const int numOfColumns, char typeOfUser) { int i, j; for(i = 0; i < numOfRows; i++) { for(j = 0; j < numOfColumns; j++) { if(grid[i][j] == '*' && typeOfUser == '0') { grid[i][j] = '0'; } else if(grid[i][j] == '*' && typeOfUser == '1') { grid[i][j] = '1'; } } } }