시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 20702 9769 7368 46.533%

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjA5OFx1Yzc3NFx1ZDJiOFx1YWMwMCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YmM4OFx1YjljY1x1YzVkMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNzU2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktuaWdodCBNb3ZlcyIsImRlc2NyaXB0aW9uIjoiPHA+TXIgU29tdXJvbG92LCBmYWJ1bG91cyBjaGVzcy1nYW1lciBpbmRlZWQsIGFzc2VydHMgdGhhdCBubyBvbmUgZWxzZSBidXQgaGltIGNhbiBtb3ZlIGtuaWdodHMgZnJvbSBvbmUgcG9zaXRpb24gdG8gYW5vdGhlciBzbyBmYXN0LiBDYW4geW91IGJlYXQgaGltPzxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGNhbGN1bGF0ZSB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgbmVlZGVkIGZvciBhIGtuaWdodCB0byByZWFjaCBvbmUgcG9pbnQgZnJvbSBhbm90aGVyLCBzbyB0aGF0IHlvdSBoYXZlIHRoZSBjaGFuY2UgdG8gYmUgZmFzdGVyIHRoYW4gU29tdXJvbG92LjxcL3A+XHJcblxyXG48cD5Gb3IgcGVvcGxlIG5vdCBmYW1pbGlhciB3aXRoIGNoZXNzLCB0aGUgcG9zc2libGUga25pZ2h0IG1vdmVzIGFyZSBzaG93biBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rbmlnaHQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTcycHg7IHdpZHRoOjE3NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBQb3NzaWJsZSBrbmlnaHQgbW92ZXMgb24gdGhlIGJvYXJkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGJlZ2lucyB3aXRoIHRoZSBudW1iZXIgbiBvZiBzY2VuYXJpb3Mgb24gYSBzaW5nbGUgbGluZSBieSBpdHNlbGYuPFwvcD5cclxuXHJcbjxwPk5leHQgZm9sbG93IG4gc2NlbmFyaW9zLiBFYWNoIHNjZW5hcmlvIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzIGNvbnRhaW5pbmcgaW50ZWdlciBudW1iZXJzLiBUaGUgXHVmYjAxcnN0IGxpbmUgc3BlY2lcdWZiMDFlcyB0aGUgbGVuZ3RoIGwgb2YgYSBzaWRlIG9mIHRoZSBjaGVzcyBib2FyZCAoNCAmbGU7IGwgJmxlOyAzMDApLiBUaGUgZW50aXJlIGJvYXJkIGhhcyBzaXplIGwgJnRpbWVzOyBsLiBUaGUgc2Vjb25kIGFuZCB0aGlyZCBsaW5lIGNvbnRhaW4gcGFpciBvZiBpbnRlZ2VycyB7MCwgLi4uLCBsJm1pbnVzOzF9JnRpbWVzOyB7MCwgLi4uLCBsJm1pbnVzOzF9IHNwZWNpZnlpbmcgdGhlIHN0YXJ0aW5nIGFuZCBlbmRpbmcgcG9zaXRpb24gb2YgdGhlIGtuaWdodCBvbiB0aGUgYm9hcmQuIFRoZSBpbnRlZ2VycyBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIGJsYW5rLiBZb3UgY2FuIGFzc3VtZSB0aGF0IHRoZSBwb3NpdGlvbnMgYXJlIHZhbGlkIHBvc2l0aW9ucyBvbiB0aGUgY2hlc3MgYm9hcmQgb2YgdGhhdCBzY2VuYXJpbzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHNjZW5hcmlvIG9mIHRoZSBpbnB1dCB5b3UgaGF2ZSB0byBjYWxjdWxhdGUgdGhlIG1pbmltYWwgYW1vdW50IG9mIGtuaWdodCBtb3ZlcyB3aGljaCBhcmUgbmVjZXNzYXJ5IHRvIG1vdmUgZnJvbSB0aGUgc3RhcnRpbmcgcG9pbnQgdG8gdGhlIGVuZGluZyBwb2ludC4gSWYgc3RhcnRpbmcgcG9pbnQgYW5kIGVuZGluZyBwb2ludCBhcmUgZXF1YWwsIGRpc3RhbmNlIGlzIHplcm8uIFRoZSBkaXN0YW5jZSBtdXN0IGJlIHdyaXR0ZW4gb24gYSBzaW5nbGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: sait2000
  • 문제의 오타를 찾은 사람: sgchoi5