시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6527 1467 861 20.221%

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

  • '.': 빈 공간
  • '#': 벽
  • '@': 상근이의 시작 위치
  • '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#[email protected]#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
W3sicHJvYmxlbV9pZCI6IjU0MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVhY2ZjIFx1YmNiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhYzc0XHViYjNjXHVjNWQwIFx1YWMwN1x1ZDYwMFx1Yzc4OFx1YjJlNC4gXHVhYzc0XHViYjNjXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1YzVkMFx1YjI5NCBcdWJkODhcdWM3NzQgXHViMGFjXHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDljXHVhZDZjXHViOTdjIFx1ZDVhNVx1ZDU3NCBcdWI2ZjBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZTQgXHVjZDA4XHViOWM4XHViMmU0LCBcdWJkODhcdWM3NDAgXHViM2Q5XHVjMTFjXHViMGE4XHViZDgxIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViZTQ4IFx1YWNmNVx1YWMwNFx1YzczY1x1Yjg1YyBcdWQzN2NcdWM4MzhcdWIwOThcdWFjMDRcdWIyZTQuIFx1YmNiZFx1YzVkMFx1YjI5NCBcdWJkODhcdWM3NzQgXHViZDk5XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjNkOVx1YzExY1x1YjBhOFx1YmQ4MSBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCAxXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmNiZFx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgXHViZDg4XHVjNzc0IFx1YzYyZVx1YWNhOFx1YzljNCBcdWNlNzggXHViNjEwXHViMjk0IFx1Yzc3NFx1YzgxYyBcdWJkODhcdWM3NzQgXHViZDk5XHVjNzNjXHViODI0XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM1ZDAgXHViZDg4XHVjNzc0IFx1YzYyZVx1YWNhOFx1YzYzNFx1YWNmYyBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViMmU0XHViOTc4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZTRjXHViNTI5XHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM1YmNcdWI5YzhcdWIwOTggXHViZTY4XHViOWFjIFx1YmU0Y1x1YjUyOVx1Yzc0NCBcdWQwYzhcdWNkOWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViZTRjXHViNTI5IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWIxMDhcdWJlNDRcdWM2NDAgXHViMTkyXHVjNzc0IHdcdWM2NDAgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgdyxoICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIGhcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IHdcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwLCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mIzM5Oy4mIzM5OzogXHViZTQ4IFx1YWNmNVx1YWMwNDxcL2xpPlxyXG5cdDxsaT4mIzM5OyMmIzM5OzogXHViY2JkPFwvbGk+XHJcblx0PGxpPiYjMzk7QCYjMzk7OiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1ODxcL2xpPlxyXG5cdDxsaT4mIzM5OyomIzM5OzogXHViZDg4PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzAxIFx1YzljMFx1YjNjNFx1YzVkMCBAXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViZTRjXHViNTI5XHVjNzQ0IFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YmU0Y1x1YjUyOVx1Yzc0NCBcdWQwYzhcdWNkOWNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQyNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpcmUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgdHJhcHBlZCBpbiBhIGJ1aWxkaW5nIGNvbnNpc3Rpbmcgb2Ygb3BlbiBzcGFjZXMgYW5kIHdhbGxzLiBTb21lIHBsYWNlcyBhcmUgb24gXHVmYjAxcmUgYW5kIHlvdSBoYXZlIHRvIHJ1biBmb3IgdGhlIGV4aXQuIFdpbGwgeW91IG1ha2UgaXQ/PFwvcD5cclxuXHJcbjxwPkF0IGVhY2ggc2Vjb25kLCB0aGUgXHVmYjAxcmUgd2lsbCBzcHJlYWQgdG8gYWxsIG9wZW4gc3BhY2VzIGRpcmVjdGx5IGNvbm5lY3RlZCB0byB0aGUgTm9ydGgsIFNvdXRoLCBFYXN0IG9yIFdlc3Qgc2lkZSBvZiBpdC4gRm9ydHVuYXRlbHksIHdhbGxzIHdpbGwgbmV2ZXIgY2F0Y2ggXHVmYjAxcmUgYW5kIHdpbGwga2VlcCB0aGUgXHVmYjAxcmUgaW5zaWRlIHRoZSBidWlsZGluZywgc28gYXMgc29vbiBhcyB5b3UgYXJlIG91dCBvZiB0aGUgYnVpbGRpbmcgeW91IHdpbGwgYmUgc2FmZS4gVG8gcnVuIHRvIGFueSBvZiB0aGUgZm91ciBvcGVuIHNwYWNlcyBhZGphY2VudCB0byB5b3UgdGFrZXMgeW91IGV4YWN0bHkgb25lIHNlY29uZC4gWW91IGNhbm5vdCBydW4gdGhyb3VnaCBhIHdhbGwgb3IgaW50byBhbiBvcGVuIHNwYWNlIHRoYXQgaXMgb24gXHVmYjAxcmUgb3IgaXMganVzdCBjYXRjaGluZyBcdWZiMDFyZSwgYnV0IHlvdSBjYW4gcnVuIG91dCBvZiBhbiBvcGVuIHNwYWNlIGF0IHRoZSBzYW1lIG1vbWVudCBpdCBjYXRjaGVzIFx1ZmIwMXJlLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIG1hcCBvZiB0aGUgYnVpbGRpbmcsIGRlY2lkZSBob3cgZmFzdCB5b3UgY2FuIGV4aXQgdGhlIGJ1aWxkaW5nLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgdyBhbmQgaCAoMSAmbGU7IHcsIGggJmxlOyAxIDAwMCk6IHRoZSB3aWR0aCBhbmQgaGVpZ2h0IG9mIHRoZSBtYXAgb2YgdGhlIGJ1aWxkaW5nLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPmggbGluZXMgd2l0aCB3IGNoYXJhY3RlcnMgZWFjaDogdGhlIG1hcCBvZiB0aGUgYnVpbGRpbmcsIGNvbnNpc3Rpbmcgb2ZcclxuXHQ8dWw+XHJcblx0XHQ8bGk+JmxzcXVvOy4mcnNxdW87OiBhIHJvb20sPFwvbGk+XHJcblx0XHQ8bGk+JmxzcXVvOyMmcnNxdW87OiBhIHdhbGwsPFwvbGk+XHJcblx0XHQ8bGk+JmxzcXVvO0AmcnNxdW87OiB5b3VyIHN0YXJ0aW5nIGxvY2F0aW9uLDxcL2xpPlxyXG5cdFx0PGxpPiZsc3F1bzsqJnJzcXVvOzogXHVmYjAxcmUuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlcmUgd2lsbCBiZSBleGFjdGx5IG9uZSAmbHNxdW87QCZyc3F1bzsgaW4gdGhlIG1hcC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciB3aGljaCBpcyB0aGUgbWluaW1hbCBudW1iZXIgb2Ygc2Vjb25kcyB0aGF0IHlvdSBuZWVkIHRvIGV4aXQgdGhlIGJ1aWxkaW5nIG9yIHRoZSBzdHJpbmcgJmxkcXVvO0lNUE9TU0lCTEUmcmRxdW87IHdoZW4gdGhpcyBpcyBub3QgcG9zc2libGUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=