Rule


ルール

東京から京都までの道路を建設せよ

入力

出力

この空間において上下左右の4方向に同じコストで移動することができるとき、東京から京都までの最短経路を探索し、図示して出力せよ。

制約

入出力例

入力

                      T                           
                                                  
                                                  
                                                  
                                                  
                                                  
         K                                        

出力例1

         *************T                           
         *                                        
         *                                        
         *                                        
         *                                        
         *                                        
         K                                        

出力例2

                      #                           
                      #                           
                      #                           
         $tsgkmctsgkmc#                           
         $                                        
         $                                        
         $                                        

出力例3

                     ##
                    ##
               ######
             ###
            ##
          ###
         ##