#!/usr/local/bin/ruby -w
# Author: js3104@cs.nyu.edu (Jack Shutzman)


  class Tamworth

    #TIME (OR MOVE COUNT) STARTS AT ZERO --> FINAL OUTPUT
    attr_reader :t 
	 # CONSTANTS
    Cow="C" 
	Farmer="F" 
	Obstacle="*" 
	Free="."                  
    Nextm = Hash["u" => "r", "r" => "d", "d" => "l", "l" => "u"] # CLOCKWISE MOVES

    def initialize
      ### VALIDATE THE INPUT BOARD IS A RECTANGLE, IF NOT RAISE EXCEPTION,
      ### FIGURE OUT THE DIMENSIONS AND MAKE THE INPUT ONE STRING


      input1=$stdin.read
      in_board=input1.split("\n")      #SPLIT BOARD LINES ACC TO newline CHAR
      m=0
      if in_board[0]
        n=in_board[0].length           #FIRST INPUT LINE DETERMINES THE BOARD'S WIDTH
      else
        n=0
      end    
      inp=""
      for ln in in_board
        raise ArgumentError, 
        "Board not a rectangle" if ln.length != n
        inp += ln 
        m += 1
      end
      inp.gsub!(/\s/,"")              # REMOVE WHITE SPACES FROM INPUT BOARD
      inp.upcase!                     # CONVERT TO UPPER CASE   
      @n, @m, @inp, @t= n, m, inp, 0  # IF THE INPUT WAS IN LOWER CASE.
      @dir=["u", "u"]                 #  BOTH COW AND JOHN START FACING UP
      @x=[]; 
      @y=[]
      @sym=[Cow, Farmer]
    end

    def init_grid
=begin	
*****************************************************************************
@grid IS A WRAPPING MATRIX FOR THE INPUT BOARD. IT WRAPS THE BOARD 
WITH OBSTACLES, SO MOVES CAN BE CALCULATED FOR EDGE SQUARES IN THE
SAME FASHION AS OTHER SQUARES.
I.E IF THE BOARD LOOKS LIKE THIS       
	                                              
..*..F           
C*..**          

THEN @grid WILL LOOK LIKE THIS

********
*..*..F*
*C*..***
********
BOTH @grid AND @inp ARE REPRESENTED AS 'FLAT' STRINGS
FIRSTLY FILL THE GRID WITH OBSTACLES, THEN EMBED THE ACTUAL BOARD IN THE GRID
     
******************************************************************************
=end

      @grid = Obstacle*((@n+2)*(@m+2)) 
      0.upto(@m-1) {|i| @grid[@n+3+i*(@n+2),@n]=@inp[i*@n,@n]}
    end

    def to_table 
      # TURN THE @grid STRING INTO A TABLE (BOARD) IN PREPARATION TO MOVE
      # JOHN AND THE COW ACCORDING TO THE RULES

      table=[]
      part=""
      0.upto(@m+1) do |j|
        0.upto(@n+1){ |k| part << (@grid[j*(@n+2),@n+2][k]) << " "}
        parts=part.split(" ")
        table.push parts
        part=""
      end
      @table=table  
    end

    def to_grid
      # CONVERT THE TWO DIMENSIONAL TABLE INTO A FLAT (@grid) TO
      # ENABLE EASY CHECKS FOR LOCATIONS OF JOHN AND THE COW
      @grid=@table.join
    end
	
    def empty?(i)
      # CHECK IF THE SQUARE THE FIGURE IS ABOUT TO MOVE TO, IS EMPTY
      x=@x[i]; y=@y[i] 
	  case @dir[i]
	  when 'u' 
	    y -= 1
	  when 'l'
	    x -= 1
	  when 'd'		
	    y += 1
	  when 'r'
	    x += 1
	  end	  
      @table[y][x] != Obstacle
    end
	
    def leave(i)
      # FREE UP THE SQUARE, THE FIGURE MOVED AWAY FROM, BUT ONLY IF
      # THE OTHER FIGURE HAD NOT MOVED THERE IN THE PREVIOUS MOVE
      i==0? j=1 : j=0
      @table[@y[i]][@x[i]]=Free if (@table[@y[i]][@x[i]] != @sym[j])
    end
    
    def next_sq(i)
      # PERFORMS THE ACTUAL MOVE (ERASE PREV. SQUARE, POPULATE NEW)
      self.leave(i)
	  
	  case @dir[i]
	  when 'u' 
	    @y[i] -= 1
	  when 'l'
	    @x[i] -= 1
	  when 'd'		
	    @y[i] += 1
	  when 'r'
	    @x[i] += 1
	  end
      @table[@y[i]][@x[i]]=@sym[i]
    end  
	  
    def chgdir(i)
      # SWITCH DIRECTIONS ACCORDING TO CLOCKWISE MOVEMENT (SET IN Nextm)
      @dir[i]=Nextm[@dir[i]]  
    end
	  	  
    def move
      # START THE MOVE PROCESS FOR BOTH FIGURES WITH AN INDEX (i)
      loc=[]
      loc[0]=@grid.index(Cow) 
	  loc[1]=@grid.index(Farmer)
	  
	  0.upto(1) do |i|
	    @y[i]=loc[i]/(@n+2)
		@x[i]=loc[i]-@y[i]*(@n+2)
	  end	
	  0.upto(1) do |i|
	    if self.empty?(i) 
		  self.next_sq(i)
		else  
		  self.chgdir(i)
		end
	  end	  
      @t+=1
      self.to_grid
    end    

    def meet
      # IF JOHN OR THE COW ARE ALONE ON THE BOARD IT MEANS THEY HAVE MET.
      # THE MOVE IS STRUCTURED SO THAT THE MOVER OCCUPIES THE NEW SQUARE,
      # UNLESS IT'S AN OBSTACLE, SO IF THEY STEPPED SIMULTANEOUSLY INTO
      # THE SAME SQUARE, JOHN CAPTURES THE MAD COW AND THE CHASE IS OVER
	  # SO THE FINAL SQUARE MAY HAVE "C" OR "F".

      !@grid.index(Cow) || !@grid.index(Farmer)
    end    

  end # class Tamworth
  
  # THIS PROGRAM IS A SIMPLE SIMULATION ON ONE BOARD WITH TWO FIGURES THAT
  # MOVE SIMILARLY, SO ONE CLASS IS SUFFICIENT. THE ALGORITHM IS AS FOLLOWS 
  # 1) READ THE INPUT, RAISE AN ERROR IF THE BOARD IS NOT A RECTANGLE
  # 2) INITIALIZE DATA STRUCTURES
  # 3) LOOP WITH THE SIMULATION UNTIL EITHER THE CHASE ENDS WITH A 'MEET'
  #    OR SUFFICIENT TIME ELAPSED (DETERMINED AS 1000 MOVES BY THE PROF.)
  #########################################################################
if $0 == __FILE__  
  begin
    chase=Tamworth.new
    chase.init_grid
    chase.to_table
    # MOVE FIGURES UNTIL CAPURE OR TIME EXPIRES
    chase.move until (chase.meet || chase.t > 1000) 
    chase.meet ? time_to_meet=chase.t : time_to_meet=0
    puts "#{time_to_meet}"
  rescue ArgumentError # ERROR HANDLING
      puts "Input Board is not a rectangle"
  end

end
