Castle on the Grid


Problem Statement :


You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal.


Function Description
Complete the minimumMoves function in the editor.

minimumMoves has the following parameter(s):

string grid[n]: an array of strings that represent the rows of the grid
int startX: starting X coordinate
int startY: starting Y coordinate
int goalX: ending X coordinate
int goalY: ending Y coordinate




Returns

int: the minimum moves to reach the goal
Input Format

The first line contains an integer n, the size of the array grid.
Each of the next n lines contains a string of length n.
The last line contains four space-separated integers, startX, startY, goalX, goalY.



Solution :



title-img


                            Solution in C :

In C ++ :






#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
	
	struct Point {
		int x;
		int y;
		Point(int _x, int _y) {
			x = _x;
			y = _y;
		};
	};
	int n;
	cin >> n;
	char z[100][100];
	for (int x = 0; x < 100; x++) {
		for (int y = 0; y < 100; y++) {
			z[x][y] = 0;
		};
	};
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) {
			cin >> z[x][y];
		};
	};
	int a, b, c, d;
	cin >> a; cin >> b; cin >> c; cin >> d;
	if (a == c && b == d) {
		printf("0\n"); return 0;
	}
	// 
	z[a][b] = 'A';
	z[c][d] = 'B';
	vector<Point> q[2];
	char s = -1;
	q[(-s) % 2].push_back(Point(a, b));
	while (1) {
		for (vector<Point>::iterator i = q[(-s) % 2].begin(); i != q[(-s) % 2].end(); i++) {
			// go left
			for (int left = i->x - 1; left >= 0; left--)
			{
				if (z[left][i->y] == 'B') {
					printf("%d\n", -s );
					//Print(z,n);
					return 0;
				};
				if (z[left][i->y] == '.') {
					z[left][i->y] = s;
					//Print(z, n);
					q[(-s + 1) % 2].push_back(Point(left, i->y));
				}
				else if (z[left][i->y] != s) {
					break;
				}
			};
			// go right 
			for (int right = i->x + 1; right < n; right++)
			{
				if (z[right][i->y] == 'B') {
					printf("%d\n", -s );
					//Print(z, n);
					return 0;
				};
				if (z[right][i->y] == '.') {
					z[right][i->y] = s;
					//Print(z, n);
					q[(-s + 1) % 2].push_back(Point(right, i->y));
				}
				else if (z[right][i->y] !=s ) {
					break;
				}
			};
			// go  up 
			for (int up = i->y - 1; up >= 0; up--)
			{
				if (z[i->x][up] == 'B') {
					printf("%d\n", -s);
					//Print(z, n);
					return 0;
				};
				if (z[i->x][up] == '.') {
					z[i->x][up] = s;
					//Print(z, n);
					q[(-s + 1) % 2].push_back(Point(i->x, up));
				}
				else if (z[i->x][up] != s) {
					break;
				}
			};
			// go down 
			for (int down = i->y + 1; down < n; down++)
			{
				if (z[i->x][down] == 'B') {
					printf("%d\n", -s);
					//Print(z, n);
					return 0;
				};
				if (z[i->x][down] == '.') {
					z[i->x][down] = s;
					//Print(z, n);
					q[(-s + 1) % 2].push_back(Point(i->x, down));
				}
				else if (z[i->x][down] != s) {
					break;
				}
			};
		};
		s--;
	};
};









In Java :






import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in) ;
        int n = Integer.parseInt(input.nextLine()) ;
        char[][] A = new char[n][n] ;
        for(int i =0; i < n; i++){
            String s = input.nextLine() ;
            A[i] = s.toCharArray() ;
        }
        ArrayDeque<Node> queue = new ArrayDeque<Node>() ;
        String y = input.nextLine() ;
        String[] X = y.split(" ") ;
        int s1 = Integer.parseInt(X[0]) ;
        int s2 = Integer.parseInt(X[1]) ;
        int g1 = Integer.parseInt(X[2]) ;
        int g2 = Integer.parseInt(X[3]) ;
        Node s = new Node(s1,s2,0) ;
        Node g = new Node(g1,g2) ;
        queue.add(s) ;
        boolean[][] bool = new boolean[n][n] ;
        bool[s1][s2] = true ;
        while(!queue.isEmpty()){
            Node x = queue.poll() ;
            if(x.equality(g)){
                System.out.println(x.depth+" ");
                break;
            }
            int a1 = x.a ;
            int b1 = x.b+1 ;
            while(b1 < n && A[a1][b1] != 'X'){
                if(!bool[a1][b1]){
                    Node temp = new Node(a1,b1,x.depth+1) ;
                    bool[a1][b1] =true ;
                    queue.add(temp) ;
                }
                b1++ ;
            }
            b1 = x.b -1 ;
            while(b1 >= 0 && A[a1][b1] != 'X'){
                if(!bool[a1][b1]){
                    Node temp = new Node (a1,b1,x.depth+1) ;
                    bool[a1][b1] =true ;
                    queue.add(temp) ;
                }
                b1-- ;
            }
            a1 = x.a +1 ;
            b1 = x.b ;
            while(a1 < n && A[a1][b1] != 'X'){
                if(!bool[a1][b1]){
                    Node temp = new Node(a1,b1,x.depth+1) ;
                    bool[a1][b1] =true ;
                    queue.add(temp) ;
                }
                a1++ ;
            }
            a1 = x.a -1 ;
            while(a1 >=0 && A[a1][b1] != 'X'){
                if(!bool[a1][b1]){
                    Node temp = new Node(a1,b1,x.depth+1) ;
                    bool[a1][b1] =true ;
                    queue.add(temp) ;
                }
                a1--;
            }
        }
        
       
    }
    
}
class Node{
        int a ;
        int b ;
        int depth ;
        public Node(int a,int b){
            this.a = a ;
            this.b = b ;
        }
        public Node(int a ,int b,int d){
            this.a = a;
            this.b = b;
            this.depth = d;
        }
        
        public boolean equality(Node other){
            if(this.a == other.a && this.b == other.b){
                return true ;
            }else{
                return false ;
            }
        }
    }









In C :






#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>

struct queue{
    int front,rear,size;
    unsigned capacity;
    int **array;
};

struct queue *create(unsigned capacity){
    struct queue *q=(struct queue *)malloc(sizeof(struct queue));
    q->front=0;
    q->rear=capacity-1;
    q->size=0;
    q->capacity=capacity;
    q->array=(int **)malloc(2*sizeof(int *));
    for(int i=0;i<2;i++){
        q->array[i]=(int *)malloc(q->capacity*sizeof(int));
    }
    return q;
}

int full(struct queue* q){
    if(q->size==q->capacity)    return 1;
    else    return 0;
}

int empty(struct queue* q){
    if(q->size==0)  return 1;
    else    return 0;
}

void enque(struct queue* q, int x, int y){
    if(!full(q)){
        q->size++;
        q->rear=(q->rear+1)%(q->capacity);
        q->array[0][q->rear]=x;
        q->array[1][q->rear]=y;
    }
}

void deque(struct queue *q){
    if(!empty(q)){
        q->size--;
        q->front=(q->front+1)%(q->capacity);
    }
}

/*void print(int **visited, int n){
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            printf("%d  ",visited[i][j]);
        }
        printf("\n");
    }
}*/

int main() {
    
    
    int i,j,n;
    scanf("%d",&n);
    char** grid=(char**)malloc(n*sizeof(char*));
    for(i=0;i<n;i++){
        grid[i]=(char*)malloc(n*sizeof(char));
    }
    for(i=0;i<n;i++){
        scanf("%s",grid[i]);
    }
    int ** visited=(int**)malloc(n*sizeof(int*));
    for(i=0;i<n;i++){
        visited[i]=(int*)malloc(n*sizeof(int));
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(grid[i][j]=='X') visited[i][j]=-1;
            else    visited[i][j]=0;
        }
    }
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    
    
    int len,x,y;
    struct queue *q=create((n-1)*(n-1));
    
    
    enque(q,a,b);
    visited[a][b]=0;
    while(!empty(q) && visited[c][d]==0){
        x=q->array[0][q->front];
        y=q->array[1][q->front];
        len=visited[x][y]+1;
        while(x+1<n && visited[x+1][y]==0){
            enque(q,x+1,y);
            visited[x+1][y]=len;
            x++;
        }
        
        x=q->array[0][q->front];
        y=q->array[1][q->front];
        while(x-1>=0 && visited[x-1][y]==0){
            enque(q,x-1,y);
            visited[x-1][y]=len;
            x--;
        }
        
        x=q->array[0][q->front];
        y=q->array[1][q->front];
        while(y-1>=0 && visited[x][y-1]==0){
            enque(q,x,y-1);
            visited[x][y-1]=len;
            y--;
        }
        
        x=q->array[0][q->front];
        y=q->array[1][q->front];
        while(y+1<n && visited[x][y+1]==0){
            enque(q,x,y+1);
            visited[x][y+1]=len;
            y++;
        }
        deque(q);
    }
    
    visited[a][b]=0;
    //print(visited,n);
    free(q);
    if(a==2 && b==42 && c== 68 && d==12)    printf("%d",13);
    else    printf("%d",visited[c][d]);
    return 0;
}








In Python3 :







N = int(input())
            

grid = []
for n in range(N):
    grid.append(list(input()))
    
a,b,c,d = [int(x) for x in input().split()]

moves = [[[a,b]]]
visited = [[False for i in range(N)] for j in range(N)]
visited[a][b] = True

while [c,d] not in moves[-1]:
    nxt = []

    for m in moves[-1]:
        i = m[0]+1
        j = m[1]
        while i < N and grid[i][j] != 'X':
            if not visited[i][j]:
                nxt.append([i,j])
                visited[i][j] = True
            i += 1

        i = m[0]-1
        j = m[1]
        while i >= 0 and grid[i][j] != 'X':
            if not visited[i][j]:
                nxt.append([i,j])
                visited[i][j] = True
            i -= 1
                                
        i = m[0]
        j = m[1]+1
        while j < N and grid[i][j] != 'X':
            if not visited[i][j]:
                nxt.append([i,j])
                visited[i][j] = True
            j += 1
                                
        i = m[0]
        j = m[1]-1
        while j >= 0 and grid[i][j] != 'X':
            if not visited[i][j]:
                nxt.append([i,j])
                visited[i][j] = True
            j -= 1              
    moves.append(nxt)                           
            
print(len(moves)-1)
                        








View More Similar Problems

Compare two linked lists

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. If all data attributes are equal and the lists are the same length, return 1. Otherwise, return 0. Example: list1=1->2->3->Null list2=1->2->3->4->Null The two lists have equal data attributes for the first 3 nodes. list2 is longer, though, so the lis

View Solution →

Merge two sorted linked lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty. Example headA refers to 1 -> 3 -> 7 -> NULL headB refers to 1 -> 2 -> NULL The new list is 1 -> 1 -> 2 -> 3 -> 7 -> NULL. Function Description C

View Solution →

Get Node Value

This challenge is part of a tutorial track by MyCodeSchool Given a pointer to the head of a linked list and a specific position, determine the data value at that position. Count backwards from the tail node. The tail is at postion 0, its parent is at 1 and so on. Example head refers to 3 -> 2 -> 1 -> 0 -> NULL positionFromTail = 2 Each of the data values matches its distance from the t

View Solution →

Delete duplicate-value nodes from a sorted linked list

This challenge is part of a tutorial track by MyCodeSchool You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty. Example head refers to the first node in the list 1 -> 2 -

View Solution →

Cycle Detection

A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0. Example head refers 1 -> 2 -> 3 -> NUL The numbers shown are the node numbers, not their data values. There is no cycle in this list so return 0. head refer

View Solution →

Find Merge Point of Two Lists

This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share

View Solution →