http://acm.pku.edu.cn/JudgeOnline/problem?id=1915
花了一個上午.......

// 廣度優先?
#include? < iostream >
using ? namespace ?std;
 int ?board[ 301 ][ 301 ];
 int ?result;
 struct ?H
 {
??? int ?row,?col;
} path1[ 100000 ],?path2[ 100000 ];
 int ?a[ 8 ][ 2 ]? = ? { { - 1 ,? 2 } , { 1 ,? 2 } , { 2 ,? 1 } , { 2 ,? - 1 } , { 1 ,? - 2 } , { - 1 ,? - 2 } , { - 2 ,? - 1 } , { - 2 ,? 1 } } ;
 int ?GYou( int ?n,? int ?br,? int ?bc,? int ?nr,? int ?nc)
 {
???? int ?dire;
???? int ?top1,top2;
???? int ?h,?g,?i,?j;????
???? int ?record;
????record? = ? 0 ;
????top1? = ? 1 ;
????top2? = ? 0 ;
????path1[top1].row? = ?br;
????path1[top1].col? = ?bc;
???? while ( true )
???? {
????????????? // ??if(result?==?2)break;
???????? for (i? = ? 1 ;?i? <= ?top1;?i ++ )
???????? {
?????? // ???????cout?<<?"top1:?"?<<?top1?<<?"?"?<<?path1[i].row?<<?"?"?<<?path1[i].col?<<?endl;
???????????? for (dire? = ? 0 ;?dire? < ? 8 ;?dire ++ )
???????????? {???
????????????????g? = ?path1[i].row? + ?a[dire][ 0 ];
????????????????h? = ?path1[i].col? + ?a[dire][ 1 ];
???????????????? if (g? == ?nr? && ?h? == ?nc) {
???????????????????record? = ? 1 ;
??????????????????? break ;
????????????????}
???????????????? if (g? >= ? 0 && ?g? < ?n && ?h? >= ? 0 && ?h? < ?n && ?board[g][h]? != ? 1 )
???????????????? {??
??????? // ??????????????cout?<<?"ha:?"?<<?path1[top1].row??<<?"?"?<<?path2[top1].col?<<?"?"?<<?g?<<?"??"?<<?h?<<?endl;
????????????????????top2 ++ ;
????????????????????path2[top2].row? = ?g;
????????????????????path2[top2].col? = ?h;
????????????????????board[g][h]? = ? 1 ;
????????????????} ?
????????????} ?????????????????
????????}
???? /* ????cout?<<?"board:?"?<<?top1?<<?endl;
????????for(i?=?0;?i?<?n;?i++)
????????{
???????????for(j?=?0;?j?<?n;?j++)
??????????????cout?<<?board[i][j];
??????????????cout?<<?endl;
????????}
???????? */
???????? if (record? == ? 1 ) {
???????????cout? << ? ++ ?result? << ?endl;
??????????? return ? 0 ;
????????}
???????? for (i? = ? 1 ;?i? <= ?top2;?i ++ )
????????????path1[i]? = ?path2[i];
????????top1? = ?top2;
????????top2? = ? 0 ;???????
????????result ++ ;?????????
????}
}
int ?main()
 {
???? int ?n,?nc,?nr,?bc,?br;
???? int ?i,?j;
???? int ?t;
????cin? >> ?t;
???? while (t -- )
???? {
???????cin? >> ?n;
???????cin? >> ?br? >> ?bc;
???????cin? >> ?nr? >> ?nc;
???????result? = ? 0 ;
??????? for (i? = ? 0 ;?i? < ?n;?i ++ )
?????????? for (j? = ? 0 ;?j? < ?n;?j ++ )
??????????????board[i][j]? = ? 0 ;
??????????????board[bc][br]? = ? 1 ;
??????? if (br? == ?nr? && ?bc? == ?nc)
??????????cout? << ?result? << ?endl;
??????? else ?
??????????GYou(n,?br,?bc,?nr,?nc);???????????
????}
???? return ? 0 ;
????
}

?