看下面的图，点1到点2，如果按你这个思路的话就是5了,但是实际答案应该是3才对。
 XXXXX
 XXXXX
 XXXXX
 XXXXX
 XXXXX
 XXXXX 
 X   X
1  X  2
XXXXXXX 

我用了一下BFS，时间复杂度有点高，用连通图做优化还是有16ms，不知道那些牛人的0ms是怎么弄的,求解。

#include <stdio.h>
#include <string.h>

//#define _DEBUGIT_
#define MAXWIDTH		80
#define MAXHEIGHT		80
#define SPSIGH			'X'

#define _abs_(a) ((a)>=0?(a):-(a))

typedef struct st_vpoint
{
	int x ;
	int y ;
}vpoint;


class CTheGame
{
public:
	void Reset() ;
	int InputMap() ;
	void PrepareMapInfo() ;
	void PrepareConnInfo(int x, int y, int nindex) ;
	int  Solve( int x1, int y1, int x2, int y2) ;
	int  BFS( int x1, int y1, int nReginIndex, int x2, int y2) ;
public:
	int			m_nRow, m_nCol ;
	char		m_MapInfo[MAXHEIGHT][MAXWIDTH];
	int			m_MapRegin[MAXHEIGHT][MAXWIDTH];
	// 做连通图时
	int			m_nReginCount ;
	vpoint		m_nQueRegin[MAXHEIGHT*MAXWIDTH] ;
	int			m_nVisit[MAXHEIGHT][MAXWIDTH] ;
};

void CTheGame::Reset() 
{
	memset(m_MapInfo,0,sizeof(m_MapInfo)) ;
	memset(m_MapRegin,0,sizeof(m_MapRegin)) ;
}
int CTheGame::InputMap() 
{
	int j , k;
	Reset() ;
	scanf("%d%d",&m_nCol,&m_nRow) ;getchar() ;
	if( m_nCol <= 0 || m_nRow <= 0)
		return 0 ;
	for( j = 1 ;j <= m_nRow;j ++)
	{
		m_MapInfo[j][0] = ' ' ;
		//fgets(m_MapInfo[j]+1,MAXWIDTH,stdin) ;
		for( k = 1; k <= m_nCol; k ++ )
			m_MapInfo[j][k] = getchar() ;
		getchar() ;// 取回车
		m_MapInfo[j][m_nCol+1] = ' ' ;
	}
	// 对图做连通图预处理
	PrepareMapInfo() ;
	return 1 ;
}

void CTheGame::PrepareConnInfo(int x, int y, int nindex) 
{
	int i = 0 ,j, tx, ty;
	int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0} ;
	m_nReginCount = 1 ;
	m_nQueRegin[0].x = x ;
	m_nQueRegin[0].y = y ;
	m_MapRegin[x][y] = nindex ;
	while( i < m_nReginCount)
	{
		for( j = 0 ; j < 4 ;j ++ )
		{
			tx = m_nQueRegin[i].x + dx[j] ;
			ty = m_nQueRegin[i].y + dy[j];
			if( tx < 0 || tx > m_nRow + 1 ||
				ty < 0 || ty > m_nCol + 1)
				continue ;
			if( m_MapInfo[tx][ty] != SPSIGH && m_MapRegin[tx][ty] <= 0)
			{
				m_MapRegin[tx][ty] = nindex ;
				m_nQueRegin[m_nReginCount].x = tx ;
				m_nQueRegin[m_nReginCount].y = ty  ;
				m_nReginCount ++ ;
			}
		}
		i ++ ;
	}

}
void CTheGame::PrepareMapInfo() 
{
	int i, j ,nIndex = 1;
	memset(m_MapRegin,0,sizeof(m_MapRegin));
	for( i = 0 ; i <= m_nRow + 1; i ++ )
	{
		for( j = 0 ; j <= m_nCol + 1 ; j ++ )
		{
			if( m_MapInfo[i][j] == SPSIGH)
			{
				m_MapRegin[i][j] = -1 ;
				continue;
			}
			if( m_MapRegin[i][j] > 0)
				continue ;
			// 不是棋子
			PrepareConnInfo(i,j,nIndex++) ;
		}
	}
#ifdef _DEBUGIT_
	for( i = 0 ; i <= m_nRow + 1; i ++ )
	{
		for( j = 0 ; j <= m_nCol + 1 ; j ++ )
		{
			printf("%-3d",m_MapRegin[i][j]) ;
		}
		printf("\n") ;
	}
#endif
}

int  CTheGame::BFS( int x1, int y1, int nReginIndex, int x2, int y2) 
{
	int i ,k = 0 ,n;
	int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0} ;
	m_nReginCount = 1 ;
	int x, y, tx, ty ;
	m_nQueRegin[0].x = x1 ;
	m_nQueRegin[0].y = y1 ;
	memset(m_nVisit,0,sizeof(m_nVisit)) ;
	do 
	{
		x = m_nQueRegin[k].x ;
		y = m_nQueRegin[k].y ;
		n = m_nVisit[m_nQueRegin[k].x][m_nQueRegin[k].y] ;
		for( i = 0 ;i < 4 ;i ++ )
		{
			tx = x ;
			ty = y ;
			while(1) // 不停地伸长
			{
				tx = tx + dx[i] ;
				ty = ty + dy[i] ;
				if( tx < 0 || tx > m_nRow + 1 ||
					ty < 0 || ty > m_nCol + 1)
					break ;
				if( tx == x2 && ty == y2)
					return n + 1;
				if( m_MapRegin[tx][ty] != nReginIndex)
					break ;
				if( m_nVisit[tx][ty] > 0 )
					break ;
				if( m_nVisit[tx][ty] == 0 )
				{
					m_nQueRegin[m_nReginCount].x = tx  ;
					m_nQueRegin[m_nReginCount].y = ty ;
					m_nVisit[tx][ty]= n + 1 ;
					m_nReginCount ++ ;
				}

			}

		}
	} while (++k < m_nReginCount);

	return 0 ;
}

int  CTheGame::Solve( int x1, int y1, int x2, int y2) 
{
	int i, j ,k,kmax=0, tx1, ty1,tx2,ty2 ,nMin = -1,t;
	// 上下左右四个方向
	int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0} ;
	int nRegion[10] , bfind = 0;
	if( _abs_(x1-x2) + _abs_(y1-y2) <= 1)
		return 1 ;
	memset(nRegion,0,sizeof(nRegion)) ;
	for( i = 0 ;i < 4 ;i ++ )
	{
		tx1 = x1 + dx[i] ;
		ty1 = y1 + dy[i] ;
		if( m_MapRegin[tx1][ty1] <= 0)
			continue ;
		bfind = 0;
		for( k = 0 ; nRegion[k] != 0 && !bfind; k ++)
		{
			if( nRegion[k] == m_MapRegin[tx1][ty1])
				bfind = 1;
		}
		if( bfind )
			continue ;
		for( j = 0 ; j < 4 ; j ++ )
		{
			tx2 = x2 + dx[j] ;
			ty2 = y2 + dy[j] ;
			if( m_MapRegin[tx1][ty1] == m_MapRegin[tx2][ty2])
			{
				t = BFS(x1,y1,m_MapRegin[tx1][ty1],x2,y2)  ;
				if( nMin == -1 || nMin > t)
					nMin = t ;
				nRegion[kmax++] = m_MapRegin[tx1][ty1] ;
				break ;
			}

		}
	}

	return nMin ;
}
int main()
{
	int x1, y1, x2, y2 , nborder = 1,ncount ;
	CTheGame s ;
	while (s.InputMap() )
	{
		printf("Board #%d:\n",nborder ++) ;
		ncount = 1 ;
		while(1)
		{
			scanf("%d%d%d%d",&y1,&x1,&y2,&x2) ;
			if( x1 <= 0)
				break ;

			x1 = s.Solve(x1,y1,x2,y2) ;
			if( x1 > 0)
				printf("Pair %d: %d segments.\n",ncount,x1) ;
			else
				printf("Pair %d: impossible.\n",ncount) ;
			ncount ++ ;
		}
		printf("\n") ;
	}
	return 0 ;
}