string_maze_solver.rb

#!usr/bin/ruby

# You are given an N x M maze. The grid consists of the characters '#' and '.'

# A '#' represents a wall, and a '.' represents a walkable tile. In addition, there is a single character 'S' representing your starting position, and a single character 'T' representing the target position. You can only move upwards, downwards, leftwards and rightwards and you can only move to walkable tiles. Also, you can't move outside the grid.

# Write a program that calculates the minimum number of moves to travel from S to T. If it is impossible to reach T from S, then output DOOMED.

# Input Format

# The first line contains two integers, N and M, separated by a single space. The next N lines each contain a string of length M consisting of '#', '.', 'S' or 'T'.

# Constraints

# 1 <= N <= 1000

# 1 <= M <= 1000

# Output Format

# Output a single line containing the minimum number of moves to travel from S to T, or DOOMED if it is impossible.

# Sample Input 0

# 7 11
# ...........
# .#########.
# ...#...#...
# S#.#.#.#.#T
# .#...#...#.
# .#########.
# ...........
# Sample Output 0

# 16
# Sample Input 1

# 4 4
# ..S#
# ..#T
# .#..
# #...
# Sample Output 1

# DOOMED
# Sample Input 2

# 3 4
# ....
# .S.#
# T...
# Sample Output 2

# 2
# Sample Input 3

# 12 19
# ...........#.......
# #.....#...#.#.....#
# ........S#T........
# ........#..........
# .......#...........
# ......#............
# .....#.............
# ....#..............
# ...#...............
# ..#................
# .#.................
# #..................
# Sample Output 3

# DOOMED

class Maze
  attr_accessor :matrix, :num_rows, :num_cols

  def initialize(n, m)
    @matrix   = Array.new(n) { Array.new(m) }
    @num_rows = n
    @num_cols = m
  end

  def fill_row(row, data)
    for j in 0..data.size-1
      @matrix[row][j] = data[j]
    end
  end

  def coordinates(str)
    for i in 0..@num_rows-1
      for j in 0..@num_cols-1
        return [i, j] if @matrix[i][j] == str
      end
    end
    return nil
  end

  def shortest_path
    return puts 'DOOMED' if(@num_rows == 1 && @num_cols == 1)

    distance = 0
    beginnig = coordinates('S')
    ending   = coordinates('T')

    puts beginnig, ending

    return puts 'DOOMED' if beginnig.nil?
    return puts 'DOOMED' if ending.nil?

    distances = Array.new(@num_rows)
    for i in 0..@num_rows-1
      distances[i] = Array.new(@num_cols, 1.0/0.0)
    end

    current_cells = [beginnig]

    while (!current_cells.empty?)
      next_cells = Array.new
      for cell in current_cells
        distances[cell[0]][cell[1]] = distance;
        # print(distances)
        add_neighbors(cell, next_cells, distances)
      end

      current_cells = next_cells
      distance+=1
    end

    if distances[ending[0]][ending[1]] != 1.0/0.0
      puts distances[ending[0]][ending[1]]
    else
      puts 'DOOMED'
    end
  end

  def to_s
    str = ''
    for i in 0..@num_rows-1
      row = ''
      for j in 0..@num_cols-1
        row += @matrix[i][j].to_s
      end
      str += row + "\n"
    end
    str
  end

  private

  def add_neighbors(cell, next_cells, distances)
    if(1..@num_rows-1).include? cell[0]
      if(distances[cell[0]-1][cell[1]] == 1.0/0.0 && @matrix[cell[0]-1][cell[1]]!='#')
        next_cells << [cell[0]-1, cell[1]] if next_cells.index([cell[0]-1, cell[1]]).nil?
      end
    end
    if (0..@num_rows-2).include? cell[0]
      if(distances[cell[0]+1][cell[1]] == 1.0/0.0 && @matrix[cell[0]+1][cell[1]]!='#')
        next_cells << [cell[0]+1, cell[1]] if next_cells.index([cell[0]+1, cell[1]]).nil?
      end
    end
    if (0..@num_cols-2).include? cell[1]
      if(distances[cell[0]][cell[1]+1] == 1.0/0.0 && @matrix[cell[0]][cell[1]+1]!='#')
        next_cells << [cell[0], cell[1]+1] if next_cells.index([cell[0], cell[1]+1]).nil?
      end
    end
    if (1..@num_cols-1).include? cell[1]
      if(distances[cell[0]][cell[1]-1] == 1.0/0.0 && @matrix[cell[0]][cell[1]-1]!='#')
        next_cells << [cell[0], cell[1]-1] if next_cells.index([cell[0], cell[1]-1]).nil?
      end
    end
  end

  def print(distances)
    for i in 0..@num_rows-1
      str = ''
      for j in 0..@num_cols-1
        str += ' | '+(distances[i][j]==1.0/0.0 ? '___' : sprintf("%03d", distances[i][j].to_s))
      end
      puts str
    end
    puts
  end
end

def clean_params(str, separator = '')
  str.chop.split(separator)
end

def create_empty_maze
  dimensions = clean_params(gets, ' ')
  dimensions = dimensions.map {|x| x.to_i}
  Maze.new(dimensions[0], dimensions[1])
end

def fill_maze
  n = @maze.num_rows
  m = @maze.num_cols
  for row in 0..n-1
    data = clean_params(gets)
    @maze.fill_row(row, data)
  end
end

def fake_maze(n = rand(1000), m = rand(1000))
  @maze = Maze.new(n,m)
  for row in 0..n-1
    for col in 0..m-1
      @maze.matrix[row][col] = ['.', '#', '.', '.', '.'].sample
    end
  end
  @maze.matrix[rand(n)][rand(m)] = 'S'
  @maze.matrix[rand(n)][rand(m)] = 'T'
  # puts @maze.to_s
end

@maze = create_empty_maze
fill_maze
# fake_maze(1000, 1000)
@maze.shortest_path