Castle on the Grid

  • + 0 comments

    Using C#:

    public static int minimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
        {
            List<StringBuilder> gridBuilder = new List<StringBuilder>();
            for (int i = 0; i < grid.Count; i++)
            {
                gridBuilder.Add(new StringBuilder(grid[i]));
            }
            Queue<int[]> queue = new Queue<int[]>();
            int n = grid.Count;
            
            // table to keep track
            var track = new int[n,n];
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    track[i,j] = 0;
    
            queue.Enqueue([startX, startY]);
                    
            while(queue.Count > 0){
                var arr = queue.Dequeue();
                int currentX = arr[0];
                int currentY = arr[1];
    
                if(currentX >= n|| currentX < 0 ||
                    currentY >=  n || currentY < 0 ||
                    gridBuilder[currentX][currentY] == 'X' ||
                    gridBuilder[currentX][currentY] == '0')
                        continue;
    
    
                // Mark as visited
                gridBuilder[currentX][currentY] = '0';
    
                if (currentX == goalX && currentY == goalY){
                    break;
                }
    
                int count = track[currentX, currentY] + 1;
                // Down
                int index = currentX + 1;
                while(index < n && gridBuilder[index][currentY] != 'X'  && gridBuilder[index][currentY] != '0'){
                     if(track[index, currentY] == 0){
                        queue.Enqueue([index, currentY]);
                        track[index, currentY] = count;
                     }
                    index++;
                }
                // Up
                index = currentX - 1;
                while(index >= 0 && gridBuilder[index][currentY] != 'X'  && gridBuilder[index][currentY] != '0'){
                    if(track[index, currentY] == 0){
                        queue.Enqueue([index, currentY]);
                        track[index, currentY] = count;
                    }
                    index--;
                }
                // Right
                index = currentY + 1;
                while(index < n && gridBuilder[currentX][index] != 'X'  && gridBuilder[currentX][index] != '0'){
                    if(track[currentX, index] == 0){
                        queue.Enqueue([currentX, index]);
                        track[currentX, index] = count;
                    }
                    index++;
                }
    
                // Left
                index = currentY - 1;
                while(index >= 0 && gridBuilder[currentX][index] != 'X'  && gridBuilder[currentX][index] != '0'){
                    if(track[currentX, index] == 0){
                        queue.Enqueue([currentX, index]);
                        track[currentX, index] = count;
                    }
                    index--;
                }
            }
            return track[goalX, goalY];
        }