CareerCup

There's a bunch of ways to solve this.

Some artificial intelligence algorithms:
- Backtracking with branch-and-bound
- Genetic algorithm
- Ant colony optimization

Convert to a graph:
- Each element that's not a block is a new vertex.
- Each vertex shall be connected to its Moore neighborhood's vertices.

Apply Dijkstra's algorithm on graph (each edge has a weight of 1).

It's easy to think of converting it to a graph and apply single source shortest path, just note that this is a sparse graph so building the graph requires O(N) time where N = m*n and a Dijkstra solution with heap requires O(NlogN) time since |E| <= 8N.

You can use Dynamic Programming to solve this.
Time Complexity : O(n*m)
Space Complexity : O(n*m)

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;
}