Write in C language not Java Description Give you a 2-D array represent a maze, in this maze, 1 is wall and 0 is a space you can walk on. You can move 4 direction, up, down, left and right. Write a program to see if a maze has a way from start to the end. Input First line of input will be a integer number represent size of the maze. Follow by n rows and n columns every row. In the maze, left top is the start and right button is end. Output if there is a way from start to the end then print "Yes", print "No" if not . Sample Input 1 5 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 Sample Output 1 Yes Sample Input 2 5 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 Sample Output 2 No
Write in C language not Java
Description
Give you a 2-D array represent a maze, in this maze, 1 is wall and 0 is a space you can walk on. You can move 4 direction, up, down, left and right.
Write a
Input
First line of input will be a integer number represent size of the maze. Follow by n rows and n columns every row. In the maze, left top is the start and right button is end.
Output
if there is a way from start to the end then print "Yes", print "No" if not .
Sample Input 1
5Sample Output 1
YesSample Input 2
5Sample Output 2
NoExpert Answer (in C language please not Java)
class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
return dfs(maze, start, destination, visited);
}
public boolean dfs(int[][] maze, int[] position, int[] destination, boolean[][] visited) {
if (visited[position[0]][position[1]]) {
return false;
}
if (position[0] == destination[0] && position[1] == destination[1]) {
return true;
}
// mark the point has been visited
visited[position[0]][position[1]] = true;
// Learn form BFS's code, we can write the code more concise
int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
for (int[] dir : dirs) {
int x = position[0];
int y = position[1];
while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
}
// Roll Back - When the program break from while loop above,
// it meas that x, y has been added dir[0], dir[1] one more time.
// But the correct answer (in the range) is less than it, so we should minus dir[0] and dir[1] here.
if (dfs(maze, new int[]{x - dir[0], y - dir[1]}, destination, visited)) {
return true;
}
}
return false;
}
}
I solve this problem in java language. May be this is helpful for you.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
