題目 2361:
信息學(xué)奧賽一本通T1450-Knight Moves
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 86 解決: 53
題目描述
編寫一個(gè)程序，計(jì)算一個(gè)騎士從棋盤上的一個(gè)格子到另一個(gè)格子所需的最小步數(shù)。騎士一步可以移動(dòng)到的位置由下圖給出。
輸入格式
第一行給出騎士的數(shù)量 n。
在接下來的 3n 行中，每 3 行描述了一個(gè)騎士。其中，
第一行一個(gè)整數(shù) L 表示棋盤的大小，整個(gè)棋盤大小為 L×L；
第二行和第三行分別包含一對整數(shù) (x,y)，表示騎士的起始點(diǎn)和終點(diǎn)。假設(shè)對于每一個(gè)騎士，起始點(diǎn)和終點(diǎn)均合理。
輸出格式
對每一個(gè)騎士，輸出一行一個(gè)整數(shù)表示需要移動(dòng)的最小步數(shù)。如果起始點(diǎn)和終點(diǎn)相同，則輸出 0。
樣例輸入
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1
樣例輸出
5 28 0
提示
對于 100% 的數(shù)據(jù)，有 4≤L≤300，保證 0≤x,y≤L?1。