Samsung Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
BFS approach. Didn't really test the code.
import java.util.*;
class MinSteps {
static class Position {
int r;
int c;
public Position(int r, int c) {
this.r = r;
this.c = c;
}
}
static int minSteps(int[][] map) {
int m = map.length;
int n = map[0].length;
LinkedList<Position> curr = new LinkedList<Position>();
curr.add(new Position(0, 0));
int steps = 0;
while(steps < m+n) {
LinkedList<Position> next = new LinkedList<Position>();
for(Position p : curr) {
int r = p.r;
int c = p.c;
if(r == m-1 && c == n-1)
return steps;
check(r+1, c, map, next);
check(r, c+1, map, next);
check(r+1, c+1, map, next);
curr = next;
}
steps++;
}
// we shouldn't reach here
return Integer.MAX_VALUE;
}
static void check(int r, int c, int[][] map, LinkedList<Position> next) {
int m = map.length;
int n = map[0].length;
if(r < m && c < n && map[r][c] == 1) {
next.add(new Position(r, c));
map[r][c] = -1;
}
}
public static void main(String[] args) {
}
}
#include<iostream>
//#define max 2147483647
using namespace std;
bool safe(int i,int j,int m,int n){
if(i>=0 && i<m && j>=0 && j<n){
return true;
}
else{
return false;
}
}
void pop(int *front,int *rear){
if(*rear == *front){
*rear=-1;
*front=-1;
}
else{
*front= *front+1;
}
}
int main(){
int t;
cin>>t;
while(t--){
int m,n;
cin>>m>>n;
int A[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>A[i][j];
}
}
int T[m][n]; int Q[m*n][2];
/* int A[7][5]={ {1,0,1,1,1},
{1,1,0,0,1},
{1,0,0,1,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,1,1},
{0,1,1,0,1}};*/
int rear=-1,front=-1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
T[i][j]=2147483647;
// cout<<T[i][j]<<" ";
}
// cout<<endl;
}
T[0][0]=0;int i=0,j=0;
rear=0;front=0;
Q[rear][0]=0;Q[rear][1]=0;
while(i<m-1 || j<n-1){
if(safe(i+1,j+1,m,n) && A[i+1][j+1]==1 && T[i+1][j+1]>1+T[i][j]){
T[i+1][j+1]=1+T[i][j];
if(rear==-1 && front ==-1){
front++;
}
rear++;
Q[rear][0]=i+1;
Q[rear][1]=j+1;
if(i+1 == m-1 && j+1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i,j+1,m,n) && A[i][j+1]==1 && T[i][j+1]>1+T[i][j]){
T[i][j+1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i;
Q[rear][1]=j+1;
if(i == m-1 && j+1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i+1,j,m,n) && A[i+1][j]==1 && T[i+1][j]>1+T[i][j]){
T[i+1][j]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i+1;
Q[rear][1]=j;
if(i+1 == m-1 && j == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i-1,j+1,m,n) && A[i-1][j+1]==1 && T[i-1][j+1]>1+T[i][j]){
T[i-1][j+1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i-1;
Q[rear][1]=j+1;
if(i-1 == m-1 && j+1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i-1,j,m,n) && A[i-1][j]==1 && T[i-1][j]>1+T[i][j]){
T[i-1][j]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i-1;
Q[rear][1]=j;
if(i-1 == m-1 && j == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i+1,j-1,m,n) && A[i+1][j-1]==1 && T[i+1][j-1]>1+T[i][j]){
T[i+1][j-1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i+1;
Q[rear][1]=j-1;
if(i+1 == m-1 && j-1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i,j-1,m,n) && A[i][j-1]==1 && T[i][j-1]>1+T[i][j]){
T[i][j-1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i;
Q[rear][1]=j-1;
if(i == m-1 && j-1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else if(safe(i-1,j-1,m,n) && A[i-1][j-1]==1 && T[i-1][j-1]>1+T[i][j]){
T[i-1][j-1]=1+T[i][j];
if(rear==-1 && front ==-1)
front++;
rear++;
Q[rear][0]=i-1;
Q[rear][1]=j-1;
if(i-1 == m-1 && j-1 == n-1){
cout<<"min path length: "<<T[m-1][n-1]<<endl;
break;
}
}
else{
pop(&front,&rear);
i=Q[front][0];
j=Q[front][1];
if(front== -1 && rear== -1){
cout<<"NO Path"<< endl;
break;
}
}
/* cout<<"i= "<<i<<" j= "<< j<<endl;
for(int k=front;k<=rear;k++){
cout<<Q[k][0]<<" "<<Q[k][1]<<endl;
}*/
}
}
return 0;
}
There's a bunch of ways to solve this.
- Victor November 24, 2014Some artificial intelligence algorithms:
- Backtracking with branch-and-bound
- Genetic algorithm
- Ant colony optimization