# -*- coding: utf-8 -*-
"""
Created on Sat Mar 10 20:40:59 2018
@author: lizihua
問題：簡單版連連看小游戲
一個分割成w*h個正方格子的矩形板上，每個正方格子可以有游戲卡，也可以沒有游戲卡
兩個游戲卡之間有一條路徑相連需滿足以下三個條件：
1.路徑只包含水平和垂直的直線段
2.路徑不能穿過別的游戲卡片
3.允許路徑臨時離開矩形板
輸入要求：
第一行包括兩個整數(shù)：w 和 h (1<=w,h<=75);w:矩形板的寬度，h:矩形板的長度
下面h行，每行包括w個字符，表示矩形板上卡片的分布情況：'X'代表這個地方有卡片；'O'代表無卡片
之后一行包括4個整數(shù)：X1，Y1，X2，Y2(1<=X1,X2<=w;1<=Y1,Y2<=h),代表兩個卡片的位置
注意：矩形板左上角的坐標是(1,1)
輸出要求：
對于每一組需要測試的游戲卡片輸出:
 若可以連接，找到線段最小路徑，輸出：k segments(k為最優(yōu)路徑的最小線段數(shù))
 若不可以連接，則輸出"impossible"
"""
import numpy as np
to=[[0,1],[1,0],[0,-1],[-1,0]] #定義方向
 
#定義遞歸函數(shù)---因為每一步搜索路徑的方式一樣
def search(now_x,now_y,end_x,end_y,step,f):
 #minstep在這里必須定義全局變量，否則，報錯
 global minstep
 if step>minstep:
 return
 if now_x==end_x and now_y==end_y:
 if step<minstep:
 minstep=step
 return
 #枚舉下一步方向 
 for i in range(4):
 x=now_x+to[i][0]
 y=now_y+to[i][1]
 
 if -1<x<(wh[1]+2) and -1<y<(wh[0]+2) and (board[x][y]=='O' and mark[x][y]==0) or (x==end_x and y==end_y and board[x][y]=='X'):
 mark[x][y]=1 #新位置有效，標記新位置
 #遞歸搜索時，step不變，否則，step+1
 #f代表方向，0,1,2,3代表東南西北
 if f==i:
 search(x,y,end_x,end_y,step,i)
 else:
 search(x,y,end_x,end_y,step+1,i)
 mark[x][y]=0
 
 
 
 
# h行w列 輸入第一行：w=wh[0];h=wh[1]
wh=input("請輸入矩形板的寬度w和長度h：").split(' ')
wh = list(map(int, wh))
 
#輸入h行，代表矩形卡片的分布情況
line=[[' ']*wh[0]]*wh[1]
for i in range(wh[1]):
 line[i]=input("請輸入第"+str(i+1)+"行卡片分布新情況：").split(' ')
#在矩形最外層加一圈'O'
board=np.array(line)
wide=np.array(['O']*wh[0])
high=np.array(['O']*(wh[1]+2))
#向board中的最下面加入一行'O'
board=np.insert(board,wh[1],values=wide,axis=0)
#向board中的最上面加入一行'O'
board=np.insert(board,0,values=wide,axis=0)
#向board中的最后一列加入一列'O'
board=np.insert(board,wh[0],values=high,axis=1)
#向board中的第0列加入一行'O'
board=np.insert(board,0,values=high,axis=1)
 
###注意：不要用mark=[[0]*(wh[0]+2)]*(wh[1]+2)
#使用上式，會使得改變某一個值時，該值所在列都會隨之一樣變化
mark=np.zeros((wh[1]+2,wh[0]+2)) #定義標記數(shù)組，并初始化
#輸入兩個卡片的位置 ,第一張卡片now(now_x,now_y);第二張卡片end(end_x,end_y) 
place=input("請輸入兩張卡片的位置：").split(' ')
place = list(map(int, place)) 
begin_x=place[0]
begin_y=place[1]
end_x=place[2]
end_y=place[3]
 
minstep=100000 #初始化minstep為一個很大的值
 #遞歸搜索路徑
search(begin_x,begin_y,end_x,end_y,0,-1)
 #輸出結果
if minstep<100000:
 print(str(minstep)+"segments")
else:
 print("impossible")