My python solution. I wrote a variation of wevefront pathfinder algorithm.
def minimumMoves(grid, startX, startY, goalX, goalY): # Create an array of arrays on integers to represent the grid grid_array = [] for x in grid: new_x = [] for char in x: match char: case ".": new_x.append(101) case "X": new_x.append(-1) grid_array.append(new_x) # Traverses the entire array from the startting cell # calculating the amount of steps needed to reach # each cell and records the result in the array grid_array[startX][startY] = 0 x_len = len(grid_array[0]) y_len = len(grid_array) current_cells = [[startX, startY]] next_value = 1 while current_cells: next_cells = [] for cell in current_cells: x = cell[0] y = cell[1] if y < x_len - 1: for y_ in range(y + 1, x_len): if grid_array[x][y_] < next_value: break grid_array[x][y_] = next_value next_cells.append([x, y_]) if y > 0: for y_ in range(y - 1, -1, -1): if grid_array[x][y_] < next_value: break grid_array[x][y_] = next_value next_cells.append([x, y_]) if x < y_len - 1: for x_ in range(x + 1, y_len): if grid_array[x_][y] < next_value: break grid_array[x_][y] = next_value next_cells.append([x_, y]) if x > 0: for x_ in range(x - 1, -1, -1): if grid_array[x_][y] < next_value: break grid_array[x_][y] = next_value next_cells.append([x_, y]) current_cells = next_cells next_value += 1 # Returns the amount of steps needed to reach the goal cell return grid_array[goalX][goalY]
JAVA gl018901
public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) { // Write your code here Queue<Integer> rq=new LinkedList<Integer>(); Queue<Integer> cq=new LinkedList<Integer>(); Queue<Integer> counterQ=new LinkedList<Integer>(); boolean[][] visit=new boolean[grid.size()][grid.size()]; for(int i=0;i<grid.size();i++){ for(int j=0;j<grid.size();j++){ visit[i][j]=false; } } rq.add(startX); cq.add(startY); counterQ.add(0); int counter=0; int[] dr={0,0,1,-1}; int[] dc={1,-1,0,0}; while(!rq.isEmpty()){ int x=rq.remove(); int y=cq.remove(); counter=counterQ.remove(); counter++; for(int i=0;i<4;i++){ int xNew=x; int yNew=y; while(true){ xNew+=dr[i]; yNew+=dc[i]; //System.out.println(xNew+","+yNew); //stop arguments if(xNew<0 || xNew>=grid.size() || yNew<0 || yNew>=grid.get(xNew).length() ||grid.get(xNew).charAt(yNew)=='X'){ System.out.println("B"); break;} //continue or get ans if(xNew==goalX &&yNew==goalY) return counter; else if(!visit[xNew][yNew]){ visit[xNew][yNew]=true; rq.add(xNew); cq.add(yNew); counterQ.add(counter); } } } } return -1; } }
in swift
struct Position: Hashable { let x: Int let y: Int } func minimumMoves(grid: [String], startX: Int, startY: Int, goalX: Int, goalY: Int) -> Int { let n = grid.count let m = grid[0].count var visited = Set<Position>() var q = [(startX, startY, 0)] let neighbors = [(1, 0), (0, 1), (0, -1), (-1, 0)] var ans = Int.max while !q.isEmpty { var nextq = [(Int, Int, Int)]() for (nx, ny, l) in q { for (dx, dy) in neighbors { var x = nx var y = ny while true { if x + dx > m - 1 || x + dx < 0 { break } if y + dy > n - 1 || y + dy < 0 { break } if grid[x + dx][grid[x + dx].index(grid[x + dx].startIndex, offsetBy: y + dy)] == "X" { break } x += dx y += dy if x == goalX && y == goalY { ans = min(ans, l + 1) break } let pos = Position(x: x, y: y) if !visited.contains(pos) { nextq.append((x, y, l + 1)) visited.insert(pos) } } } } q = nextq } return ans != Int.max ? ans : -1 }
# Author : Tonmoy M # Author URL : https://qinetique.github.io # Problem : Castle on the Grid # Sub-Domain : Interview Preparation kit | Stacks and Queues # Domain : HackerRank # Problem URL : https://www.hackerrank.com/challenges/castle-on-the-grid/problem?h_l=interview&isFullScreen=true&playlist_slugs%5B%5D%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D%5B%5D=stacks-queues import sys from collections import deque def minimumMoves(g, startX, startY, goalX, goalY): def next(g, p, q, v): r, c = len(g), len(g[-1]) cx, cy, cs = p for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nx, ny = cx, cy while True: nx, ny = nx + dx, ny + dy if r > nx >= 0 and c > ny >= 0 and g[nx][ny] != 'X': if (nx, ny) not in v: v.add((nx, ny)) q.append((nx, ny, cs + 1)) else: break dq = deque() v = {startX, startY} dq.append((startX, startY, 0)) while dq: cl = dq.popleft() if cl[:2] == (goalX, goalY): return cl[2] else: next(g, cl, dq, v) if __name__ == '__main__': fptr = sys.stdout n = int(input().strip()) grid = [] for _ in range(n): grid_item = input() grid.append(grid_item) first_multiple_input = input().rstrip().split() startX = int(first_multiple_input[0]) startY = int(first_multiple_input[1]) goalX = int(first_multiple_input[2]) goalY = int(first_multiple_input[3]) result = minimumMoves(grid, startX, startY, goalX, goalY) fptr.write(str(result) + '\n') fptr.close()
Well, after several hours in three days, I finally made it.
So, it's clear that BFS is an easy method, which was what I applied as well. A tricky problem is that if a point was ever traversed by a horizontal path, then the point is also available for a vertical path. How to achieve such an effect? I applied two matrix named vertical and horizontal.
When you find a vertical path, which means you are moving the index of row, you need to check if the path has ever been used by any other vertical paths already. If no, you can use it even though some points in the vertical path has been used in some horizontal paths already.int minimumMoves(vector<string> grid, int startX, int startY, int goalX, int goalY) { int res = 0; vector<vector<int>> orientations {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vector<vector<bool>> horizontal(grid.size(), vector<bool>(grid[0].size(), false)); vector<vector<bool>> vertical(grid.size(), vector<bool>(grid[0].size(), false)); queue<pair<int,int>> q; q.push(make_pair(startX, startY)); grid[startX][startY] = '*'; horizontal[startX][startY] = true; vertical[startX][startY] = true; while (!q.empty()) { int q_size = q.size(); for (int i = 0; i < q_size; i++) { startX = q.front().first; startY = q.front().second; // cout << "x: " << startX << " y: " << startY << endl; q.pop(); for (const auto& ori : orientations) { int newX = startX; int newY = startY; if (newX == goalX && newY == goalY) { return res; } if (ori[0] != 0) { int tmpX = newX; // cout << "tmpX + ori[0]: " << tmpX + ori[0] << endl; while (tmpX + ori[0] >= 0 && tmpX + ori[0] < grid.size() && ((grid[tmpX + ori[0]][newY] == '.') || (grid[tmpX + ori[0]][newY] == '*' && vertical[tmpX + ori[0]][newY] == false))) { grid[tmpX + ori[0]][newY] = '*'; vertical[tmpX + ori[0]][newY] = true; q.push(make_pair(tmpX + ori[0], newY)); tmpX += ori[0]; // cout << "ori[0] != 0\n"; } } else if (ori[1] != 0) { int tmpY = newY; while (tmpY + ori[1] >= 0 && tmpY + ori[1] < grid[0].size() && ((grid[newX][tmpY + ori[1]] == '.') || (grid[newX][tmpY + ori[1]] == '*' && horizontal[newX][tmpY + ori[1]] == false))) { grid[newX][tmpY + ori[1]] = '*'; horizontal[newX][tmpY + ori[1]] = true; q.push(make_pair(newX, tmpY + ori[1])); tmpY += ori[1]; // cout << "ori[1] != 0\n"; } } } } res++; } return res; }
Load more conversations
Sort 321 Discussions, By:
Please Login in order to post a comment