시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 63 18 15 46.875%

문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최소값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

  • .: 깨끗한 칸
  • *: 더러운 칸
  • x: 가구
  • o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최소값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

예제 입력 1

7 5
.......
.o...*.
.......
.*...*.
.......
15 13
.......x.......
...o...x....*..
.......x.......
.......x.......
.......x.......
...............
xxxxx.....xxxxx
...............
.......x.......
.......x.......
.......x.......
..*....x....*..
.......x.......
10 10
..........
..o.......
..........
..........
..........
.....xxxxx
.....x....
.....x.*..
.....x....
.....x....
0 0

예제 출력 1

8
49
-1

힌트

W3sicHJvYmxlbV9pZCI6IjQ5OTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWJkMDcgXHVjY2FkXHVjMThjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWJjMjlcdWM3NDQgXHViODVjXHViZDA3IFx1Y2NhZFx1YzE4Y1x1YWUzMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjY2FkXHVjMThjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1Yjg1Y1x1YmQwNyBcdWNjYWRcdWMxOGNcdWFlMzBcdWIyOTQgXHVjNzIwXHVjODAwXHVhYzAwIFx1YzljMVx1YzgxMSBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjMTI0XHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMyOVx1Yzc0MCBcdWQwNmNcdWFlMzBcdWFjMDAgMSZ0aW1lczsxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWNlNzhcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViODVjXHViZDA3IFx1Y2NhZFx1YzE4Y1x1YWUzMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIzYzQgMSZ0aW1lczsxXHVjNzc0XHViMmU0LiBcdWNlNzhcdWM3NDAgXHVhZTY4XHViMDU3XHVkNTVjIFx1Y2U3OFx1YWNmYyBcdWIzNTRcdWI3ZWNcdWM2YjQgXHVjZTc4XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yjg1Y1x1YmQwNyBcdWNjYWRcdWMxOGNcdWFlMzBcdWIyOTQgXHViMzU0XHViN2VjXHVjNmI0IFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NzRcdWMxMWMgXHVhZTY4XHViMDU3XHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzdjXHViZDgwIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWFjMDBcdWFkNmNcdWFjMDAgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzAwXHVhZDZjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjNjNCAxJnRpbWVzOzFcdWM3NzRcdWIyZTQuIFx1Yjg1Y1x1YmQwNyBcdWNjYWRcdWMxOGNcdWFlMzBcdWIyOTQgXHVhYzAwXHVhZDZjXHVhYzAwIFx1YjE5M1x1YzVlY1x1YzljNCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yjg1Y1x1YmQwN1x1Yzc0MCBcdWQ1NWMgXHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMsIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHViODVjXHViZDA3XHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM3NDQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzI5XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzNTRcdWI3ZWNcdWM2YjQgXHVjZTc4XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWFlNjhcdWIwNTdcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMjlcdWM3NTggXHVhYzAwXHViODVjIFx1ZDA2Y1x1YWUzMCB3XHVjNjQwIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzAgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgdywgaCAmbGU7IDIwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIGhcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMjlcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IDRcdWFjMDBcdWM5YzAgXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWM3NTggXHVjNzU4XHViYmY4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+LjxcL2NvZGU+OiBcdWFlNjhcdWIwNTdcdWQ1NWMgXHVjZTc4PFwvbGk+XHJcblx0PGxpPjxjb2RlPio8XC9jb2RlPjogXHViMzU0XHViN2VjXHVjNmI0IFx1Y2U3ODxcL2xpPlxyXG5cdDxsaT48Y29kZT54PFwvY29kZT46IFx1YWMwMFx1YWQ2YzxcL2xpPlxyXG5cdDxsaT48Y29kZT5vPFwvY29kZT46IFx1Yjg1Y1x1YmQwNyBcdWNjYWRcdWMxOGNcdWFlMzBcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1ODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjM1NFx1YjdlY1x1YzZiNCBcdWNlNzhcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDEwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1Yjg1Y1x1YmQwNyBcdWNjYWRcdWMxOGNcdWFlMzBcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViMzU0XHViN2VjXHVjNmI0IFx1Y2U3OFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhZTY4XHViMDU3XHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0Jm5ic3A7XHViMzU0XHViN2VjXHVjNmI0IFx1Y2U3OFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTkxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2xlYW5pbmcgUm9ib3QiLCJkZXNjcmlwdGlvbiI6IjxwPkhlcmUsIHdlIHdhbnQgdG8gc29sdmUgcGF0aCBwbGFubmluZyBmb3IgYSBtb2JpbGUgcm9ib3QgY2xlYW5pbmcgYSByZWN0YW5ndWxhciByb29tIGZsb29yIHdpdGggZnVybml0dXJlLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgcm9vbSBmbG9vciBwYXZlZCB3aXRoIHNxdWFyZSB0aWxlcyB3aG9zZSBzaXplIGZpdHMgdGhlIGNsZWFuaW5nIHJvYm90ICgxICZ0aW1lczsgMSkuIFRoZXJlIGFyZSAmIzM5O2NsZWFuIHRpbGVzJiMzOTsgYW5kICYjMzk7ZGlydHkgdGlsZXMmIzM5OywgYW5kIHRoZSByb2JvdCBjYW4gY2hhbmdlIGEgJiMzOTtkaXJ0eSB0aWxlJiMzOTsgdG8gYSAmIzM5O2NsZWFuIHRpbGUmIzM5OyBieSB2aXNpdGluZyB0aGUgdGlsZS4gQWxzbyB0aGVyZSBtYXkgYmUgc29tZSBvYnN0YWNsZXMgKGZ1cm5pdHVyZSkgd2hvc2Ugc2l6ZSBmaXRzIGEgdGlsZSBpbiB0aGUgcm9vbS4gSWYgdGhlcmUgaXMgYW4gb2JzdGFjbGUgb24gYSB0aWxlLCB0aGUgcm9ib3QgY2Fubm90IHZpc2l0IGl0LiBUaGUgcm9ib3QgbW92ZXMgdG8gYW4gYWRqYWNlbnQgdGlsZSB3aXRoIG9uZSBtb3ZlLiBUaGUgdGlsZSBvbnRvIHdoaWNoIHRoZSByb2JvdCBtb3ZlcyBtdXN0IGJlIG9uZSBvZiBmb3VyIHRpbGVzIChpLmUuLCBlYXN0LCB3ZXN0LCBub3J0aCBvciBzb3V0aCkgYWRqYWNlbnQgdG8gdGhlIHRpbGUgd2hlcmUgdGhlIHJvYm90IGlzIHByZXNlbnQuIFRoZSByb2JvdCBtYXkgdmlzaXQgYSB0aWxlIHR3aWNlIG9yIG1vcmUuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2ggY29tcHV0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIGZvciB0aGUgcm9ib3QgdG8gY2hhbmdlIGFsbCAmIzM5O2RpcnR5IHRpbGVzJiMzOTsgdG8gJiMzOTtjbGVhbiB0aWxlcyYjMzk7LCBpZiBldmVyIHBvc3NpYmxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIG1hcHMsIGVhY2ggcmVwcmVzZW50aW5nIHRoZSBzaXplIGFuZCBhcnJhbmdlbWVudCBvZiB0aGUgcm9vbS4gQSBtYXAgaXMgZ2l2ZW4gaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbncgaFxyXG5jPHN1Yj4xMTxcL3N1Yj4gYzxzdWI+MTI8XC9zdWI+IGM8c3ViPjEzPFwvc3ViPiAuLi4gYzxzdWI+MXc8XC9zdWI+XHJcbmM8c3ViPjIxPFwvc3ViPiBjPHN1Yj4yMjxcL3N1Yj4gYzxzdWI+MjM8XC9zdWI+IC4uLiBjPHN1Yj4ydzxcL3N1Yj5cclxuLi4uXHJcbmM8c3ViPmgxPFwvc3ViPiBjPHN1Yj5oMjxcL3N1Yj4gYzxzdWI+aDM8XC9zdWI+IC4uLiBjPHN1Yj5odzxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5UaGUgaW50ZWdlcnMgdyBhbmQgaCBhcmUgdGhlIGxlbmd0aHMgb2YgdGhlIHR3byBzaWRlcyBvZiB0aGUgZmxvb3Igb2YgdGhlIHJvb20gaW4gdGVybXMgb2Ygd2lkdGhzIG9mIGZsb29yIHRpbGVzLiB3IGFuZCBoIGFyZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMjAuIFRoZSBjaGFyYWN0ZXIgYzxzdWI+eXg8XC9zdWI+IHJlcHJlc2VudHMgd2hhdCBpcyBpbml0aWFsbHkgb24gdGhlIHRpbGUgd2l0aCBjb29yZGluYXRlcyAoeCwgeSkgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mIzM5Ozxjb2RlPi48XC9jb2RlPiYjMzk7IDogYSBjbGVhbiB0aWxlPFwvbGk+XHJcblx0PGxpPiYjMzk7PGNvZGU+KjxcL2NvZGU+JiMzOTsgOiBhIGRpcnR5IHRpbGUmbmJzcDs8XC9saT5cclxuXHQ8bGk+JiMzOTs8Y29kZT54PFwvY29kZT4mIzM5OyA6IGEgcGllY2Ugb2YgZnVybml0dXJlIChvYnN0YWNsZSkmbmJzcDs8XC9saT5cclxuXHQ8bGk+JiMzOTs8Y29kZT5vPFwvY29kZT4mIzM5OyA6IHRoZSByb2JvdCAoaW5pdGlhbCBwb3NpdGlvbik8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiB0aGUgbWFwIHRoZSBudW1iZXIgb2YgJiMzOTtkaXJ0eSB0aWxlcyYjMzk7IGRvZXMgbm90IGV4Y2VlZCAxMC4gVGhlcmUgaXMgb25seSBvbmUgJiMzOTtyb2JvdCYjMzk7LjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG1hcCwgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzLiBJZiB0aGUgbWFwIGluY2x1ZGVzICYjMzk7ZGlydHkgdGlsZXMmIzM5OyB3aGljaCB0aGUgcm9ib3QgY2Fubm90IHJlYWNoLCB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCAtMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=