Fortinet Interview Question
Software Engineer / DevelopersCountry: Canada
Interview Type: Written Test
After move to (x, y), it's not enough to only try (x+1,y) and (x, y+1).
I think should try all the other 3 directions except the one that just come from.
#include <stdio.h>
#include <stdbool.h>
int n=5;
int M[5][5]={{1,1,0,1,0},{1,0,1,0,1},{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,0}};
int sol[5][5] = {0};
bool solve(int M[n][n], int x, int y, int sol[n][n]);
bool issafe (int M[n][n], int i, int j)
{
if (i >= 0 && i < n && j >= 0 && j <n && M[i][j] == 1)
return 1;
return 0;
}
bool Mazepath(int M[n][n])
{
if(!solve(M, 0,0,sol))
return false;
print(sol);
return true;
}
void print (int sol[n][n])
{
for(int i =0; i< n; i++) {
for(int j=0; j< n; j++) {
printf("%d\n", sol[i][j]);
}}
}
bool solve(int M[n][n], int x, int y, int sol[n][n])
{
if (x == n-1 && y ==n-1){
sol[x][y] =1; return true;
}
if(issafe(M, x,y)==true){
sol[x][y]=1;
if(solve(M,x+1,y,sol)) ;return true;
if(solve(M,x,y+1,sol)) ;return true;
//if(solve(M,x-1,y,sol)) return true;
//if(solve(M,x,y-1,sol)) return true;
sol[x][y]=0;
return false;
}
return true;
}
int main()
{
Mazepath(M);
return 0;
}
#include <stdio.h>
#include <stdbool.h>
int n=5;
int M[5][5]={{1,1,0,1,0},{1,0,1,0,1},{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,0}};
int sol[5][5] = {0};
bool solve(int M[n][n], int x, int y, int sol[n][n]);
bool issafe (int M[n][n], int i, int j)
{
if (i >= 0 && i < n && j >= 0 && j <n && M[i][j] == 1)
return 1;
return 0;
}
bool Mazepath(int M[n][n])
{
if(!solve(M, 0,0,sol))
return false;
print(sol);
return true;
}
void print (int sol[n][n])
{
for(int i =0; i< n; i++) {
for(int j=0; j< n; j++) {
printf("%d\n", sol[i][j]);
}}
}
bool solve(int M[n][n], int x, int y, int sol[n][n])
{
if (x == n-1 && y ==n-1){
sol[x][y] =1; return true;
}
if(issafe(M, x,y)==true){
sol[x][y]=1;
if(solve(M,x+1,y,sol)) ;return true;
if(solve(M,x,y+1,sol)) ;return true;
//if(solve(M,x-1,y,sol)) return true;
//if(solve(M,x,y-1,sol)) return true;
sol[x][y]=0;
return false;
}
return true;
}
int main()
{
Mazepath(M);
return 0;
}
#include <stdio.h>
#include <stdbool.h>
int n=5;
int M[5][5]={{1,1,0,1,0},{1,0,1,0,1},{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,0}};
int sol[5][5] = {0};
bool solve(int M[n][n], int x, int y, int sol[n][n]);
bool issafe (int M[n][n], int i, int j)
{
if (i >= 0 && i < n && j >= 0 && j <n && M[i][j] == 1)
return 1;
return 0;
}
bool Mazepath(int M[n][n])
{
if(!solve(M, 0,0,sol))
return false;
print(sol);
return true;
}
void print (int sol[n][n])
{
for(int i =0; i< n; i++) {
for(int j=0; j< n; j++) {
printf("%d\n", sol[i][j]);
}}
}
bool solve(int M[n][n], int x, int y, int sol[n][n])
{
if (x == n-1 && y ==n-1){
sol[x][y] =1; return true;
}
if(issafe(M, x,y)==true){
sol[x][y]=1;
if(solve(M,x+1,y,sol)) ;return true;
if(solve(M,x,y+1,sol)) ;return true;
//if(solve(M,x-1,y,sol)) return true;
//if(solve(M,x,y-1,sol)) return true;
sol[x][y]=0;
return false;
}
return true;
}
int main()
{
Mazepath(M);
return 0;
}
{
#define RESULT_ROW 1024
#define N 5
bool back_tracking(int M[N][N],int x,int y,int **result,int *result_index){
////终止条件
if (x == N - 1 && y == N - 1 && M[x][y] == 0){
result[*result_index][0]= x;
result[*result_index][1] = y;
result_index++;
return true;
}
result[*result_index][0]= x;
result[*result_index][1] = y;
(*result_index)++;
if (x> N-1 || y> N-1) return false;
if (M[x][y] == 1){
return false;
}
if(back_tracking(M, x+1,y,result,result_index) == false){
(*result_index)--;
if (back_tracking(M, x,y+1,result,result_index) == false){
(*result_index)--;
return false;
}
}
return true;
}
bool find_one_path(int M[N][N],int x,int y){
int **result = (int **)malloc(sizeof(int*)*RESULT_ROW);
int result_count = 0;
for (int i = 0 ; i < RESULT_ROW;i++)
result[i]= (int *)malloc(sizeof(int)*2);
bool ret = back_tracking(M,0,0,result,&result_count);
if (ret){
printf("We find the path to the destination\n");
for(int i = 0 ;i < result_count -1 ;i++){
printf("(%d %d) ->",result[i][0],result[i][1]);
}
printf("(%d %d)",result[result_count -2][0],result[result_count -2][1]);
}
else
{
printf("We can not find the path to the destination\n");
}
for (int i = 0 ; i < RESULT_ROW;i++)
free(result[i]);
free(result);
}
void main(){
int M[N][N]={{0,0,0,1,0},{1,0,1,0,1},{1,0,0,0,0},{1,0,1,0,1},{0,0,1,0,0}};
return (find_one_path(M,0,0));
}
}
#define RESULT_ROW 1024
#define N 5
bool back_tracking(int M[N][N],int x,int y,int **result,int *result_index){
////终止条件
if (x == N - 1 && y == N - 1 && M[x][y] == 0){
result[*result_index][0]= x;
result[*result_index][1] = y;
result_index++;
return true;
}
result[*result_index][0]= x;
result[*result_index][1] = y;
(*result_index)++;
if (x> N-1 || y> N-1) return false;
if (M[x][y] == 1){
return false;
}
if(back_tracking(M, x+1,y,result,result_index) == false){
(*result_index)--;
if (back_tracking(M, x,y+1,result,result_index) == false){
(*result_index)--;
return false;
}
}
return true;
}
bool find_one_path(int M[N][N],int x,int y){
int **result = (int **)malloc(sizeof(int*)*RESULT_ROW);
int result_count = 0;
for (int i = 0 ; i < RESULT_ROW;i++)
result[i]= (int *)malloc(sizeof(int)*2);
bool ret = back_tracking(M,0,0,result,&result_count);
if (ret){
printf("We find the path to the destination\n");
for(int i = 0 ;i < result_count -1 ;i++){
printf("(%d %d) ->",result[i][0],result[i][1]);
}
printf("(%d %d)",result[result_count -2][0],result[result_count -2][1]);
}
else
{
printf("We can not find the path to the destination\n");
}
for (int i = 0 ; i < RESULT_ROW;i++)
free(result[i]);
free(result);
}
void main(){
int M[N][N]={{0,0,0,1,0},{1,0,1,0,1},{1,0,0,0,0},{1,0,1,0,1},{0,0,1,0,0}};
return (find_one_path(M,0,0));
}
Here N=9
- Aashish June 23, 2012