C Program The Problem Jimmy, the new lab assistant has made new cages for the la

Question

C Program

The Problem

Jimmy, the new lab assistant has made new cages for the lab rabbits, Pete and Bob. Unfortunately, these new cages are more like mazes with walls in every direction. Help determine if the rabbits are in the same section of the cage or different sections. Each rabbit can hop one square directly up, down, right or left. They can hop as many times as they want from one free square to another. Each rabbit must stay on the grid.

The Input

Each input will start with a single integer T (1 T 100) on the first line. The number T will denote the number of test cases that follow. Each test case will begin with two integers, R and C (1 R, C 10) separated by a space. Each of the next R lines will contain C characters of either '_','#', 'P' or 'B'. This will form a grid that represents the cage. A '_' represents a cell free of obstructions, '#' represents a wall, 'P' is Pete's location and 'B' is Bob's location. Each grid is guaranteed to have one and only one P and B.

The Output

For each test case output a single line containing "yes" if Pete and Bob are in the same section of the cage and "no" if they are not in the same section of the cage.

Sample Input

4

2 2

P#

#C

2 2

P_

C_

8 7

__P____

####_##

_____#_

_____#C

##_###_

_____#_

___#_#_

___#___

5 7

__P____

####_##

_____#_

_____#C

##_###_

Sample Output

no

yes

yes

no

Explanation / Answer

#include<stdio.h>

#define n 4

bool mazing(int maze[n][n], int x, int y, int result[n][n]);

//Checking valid coordinates
bool check(int maze[n][n], int x, int y)
{
if(x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1)
return true;

return false;
}
//Trying backtracking
bool solveMaze(int maze[n][n])
{
int result[n][n] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

if(mazing(maze, 0, 0, result) == false)
{
printf("Solution doesn't exist");
return false;
}

dispMaze(result);
return true;
}

bool mazing(int maze[n][n], int x, int y, int result[n][n])
{
if(x == n-1 && y == n-1)
{
result[x][y] = 1;
return true;
}

// Check if coordinate[x][y] is valid
if(check(maze, x, y) == true)
{
result[x][y] = 1;

//x direction ahead

if (mazing(maze, x+1, y, result) == true)
return true;

//y direction ahead
if (mazing(maze, x, y+1, result) == true)
return true;

// If none, then backtrack.
result[x][y] = 0;
return false;
}   

return false;
}

int main()
{
int maze[n][n] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};

solveMaze(maze);
return 0;
}

void dispMaze(int result[n][n])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
printf(" %d ", result[i][j]);
printf(" ");
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.