시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8556 3658 2802 42.403%

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0
W3sicHJvYmxlbV9pZCI6Ijc1NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWM3NzRcdWQyYjhcdWM3NTggXHVjNzc0XHViM2Q5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjYjRcdWMyYTRcdWQzMTAgXHVjNzA0XHVjNWQwIFx1ZDU1YyBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMmU0LiBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIwOThcdWM3NzRcdWQyYjhcdWIyOTQgXHViYTg3IFx1YmM4OCBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHVjNzc0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rbmlnaHQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTcycHg7IHdpZHRoOjE3NXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzEzOCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NTggXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzQgbCg0ICZsZTsmbmJzcDtsICZsZTsgMzAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgbCAmdGltZXM7IGxcdWM3NzRcdWIyZTQuIFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YjQ1MCBcdWMyMThcdWM3NTggXHVjMzBkIHswLCAuLi4sIGwtMX0gJnRpbWVzOyB7MCwgLi4uLCBsLTF9XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVhY2ZjIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHVjNzc0XHVkMmI4XHVhYzAwIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjZTc4LCBcdWIwOThcdWM3NzRcdWQyYjhcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWJhODcgXHViYzg4XHViOWNjXHVjNWQwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NTYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS25pZ2h0IE1vdmVzIiwiZGVzY3JpcHRpb24iOiI8cD5NciBTb211cm9sb3YsIGZhYnVsb3VzIGNoZXNzLWdhbWVyIGluZGVlZCwgYXNzZXJ0cyB0aGF0IG5vIG9uZSBlbHNlIGJ1dCBoaW0gY2FuIG1vdmUga25pZ2h0cyBmcm9tIG9uZSBwb3NpdGlvbiB0byBhbm90aGVyIHNvIGZhc3QuIENhbiB5b3UgYmVhdCBoaW0/PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3ZlcyBuZWVkZWQgZm9yIGEga25pZ2h0IHRvIHJlYWNoIG9uZSBwb2ludCBmcm9tIGFub3RoZXIsIHNvIHRoYXQgeW91IGhhdmUgdGhlIGNoYW5jZSB0byBiZSBmYXN0ZXIgdGhhbiBTb211cm9sb3YuPFwvcD5cclxuXHJcbjxwPkZvciBwZW9wbGUgbm90IGZhbWlsaWFyIHdpdGggY2hlc3MsIHRoZSBwb3NzaWJsZSBrbmlnaHQgbW92ZXMgYXJlIHNob3duIGluIEZpZ3VyZSAxLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tuaWdodC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzJweDsgd2lkdGg6MTc1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IFBvc3NpYmxlIGtuaWdodCBtb3ZlcyBvbiB0aGUgYm9hcmQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgYmVnaW5zIHdpdGggdGhlIG51bWJlciBuIG9mIHNjZW5hcmlvcyBvbiBhIHNpbmdsZSBsaW5lIGJ5IGl0c2VsZi48XC9wPlxyXG5cclxuPHA+TmV4dCBmb2xsb3cgbiBzY2VuYXJpb3MuIEVhY2ggc2NlbmFyaW8gY29uc2lzdHMgb2YgdGhyZWUgbGluZXMgY29udGFpbmluZyBpbnRlZ2VyIG51bWJlcnMuIFRoZSBcdWZiMDFyc3QgbGluZSBzcGVjaVx1ZmIwMWVzIHRoZSBsZW5ndGggbCBvZiBhIHNpZGUgb2YgdGhlIGNoZXNzIGJvYXJkICg0ICZsZTsgbCAmbGU7IDMwMCkuIFRoZSBlbnRpcmUgYm9hcmQgaGFzIHNpemUgbCAmdGltZXM7IGwuIFRoZSBzZWNvbmQgYW5kIHRoaXJkIGxpbmUgY29udGFpbiBwYWlyIG9mIGludGVnZXJzIHswLCAuLi4sIGwmbWludXM7MX0mdGltZXM7IHswLCAuLi4sIGwmbWludXM7MX0gc3BlY2lmeWluZyB0aGUgc3RhcnRpbmcgYW5kIGVuZGluZyBwb3NpdGlvbiBvZiB0aGUga25pZ2h0IG9uIHRoZSBib2FyZC4gVGhlIGludGVnZXJzIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgYmxhbmsuIFlvdSBjYW4gYXNzdW1lIHRoYXQgdGhlIHBvc2l0aW9ucyBhcmUgdmFsaWQgcG9zaXRpb25zIG9uIHRoZSBjaGVzcyBib2FyZCBvZiB0aGF0IHNjZW5hcmlvPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggc2NlbmFyaW8gb2YgdGhlIGlucHV0IHlvdSBoYXZlIHRvIGNhbGN1bGF0ZSB0aGUgbWluaW1hbCBhbW91bnQgb2Yga25pZ2h0IG1vdmVzIHdoaWNoIGFyZSBuZWNlc3NhcnkgdG8gbW92ZSBmcm9tIHRoZSBzdGFydGluZyBwb2ludCB0byB0aGUgZW5kaW5nIHBvaW50LiBJZiBzdGFydGluZyBwb2ludCBhbmQgZW5kaW5nIHBvaW50IGFyZSBlcXVhbCwgZGlzdGFuY2UgaXMgemVyby4gVGhlIGRpc3RhbmNlIG11c3QgYmUgd3JpdHRlbiBvbiBhIHNpbmdsZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2001 3번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: sgchoi5