시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 27 12 12 44.444%

문제

MxN개의 칸으로 구성된 미로가 있다. 각 칸에는 4개의 인접한 곳으로 이동할 수 있는 문이 있다. 이 4개의 문은 한 번에 한 개만 열리며, A에서 B로 가는 문과 B에서 A로 가는 문은 별개로 작동한다. 문들의 초기 상태는 입력에서 주어지며, 1분에 한 번 시계 방향으로 90도씩 바뀐다.

미로에는 총 K개의 보물상자가 있다. 당신은 1분에 문이 열린 방향으로 한 칸 움직이거나 원하는 방향의 문이 열릴 때까지 기다릴 수 있다.

미로에서 당신이 시작하게 될 위치는 (1, 1)이며, 목표는 모든 보물 상자를 가지고 (M, N)에 도달하는 것이다. 물론 보물 상자를 전부 가지고 있지 않더라도 (M, N)에는 갈 수 있지만 미로를 탈출하기 위해서는 모든 보물 상자를 모아서 가야 한다.

이 때 미로를 탈출하기 위한 최소 시간을 구하시오.

입력

입력 데이터는 여러 개의 테스트 케이스로 구성되어 있다. 각각의 입력은 두 정수 M, N(2 ≤ M, N ≤ 100)으로 시작하며, 다음 M개의 줄에는 초기에 문이 열린 방향을 나타내는 N, E, S, W중 하나의 문자가 각 줄에 N개씩 주어진다.

예를 들어 칸의 위치가 (r, c)라면, N, E, S, W는 각각 (r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)로 가는 문이 열려 있다는 것을 의미한다.

이후 보물 상자의 개수인 K(1 ≤ K ≤ 8)가 주어지고, 그 다음 K개의 줄에 각각의 보물상자의 위치를 나타내는 R, C가 주어진다. 한 칸에 여러 개의 보물 상자가 있는 경우는 없으며 보물 상자의 위치가 (1, 1)이거나 (M, N)인 경우도 없다.

마지막 줄의 "0 0"은 입력의 끝을 알린다.

출력

각각의 테스트 케이스에 대해 미로를 탈출하기 위한 최소 시간을 출력한다.

예제 입력 1

2 2
EE
NN
1
1 2
0 0

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE1NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxODBcdWI3N2NcdWM2YjQgXHViYmY4XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5NeE5cdWFjMWNcdWM3NTggXHVjZTc4XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWJiZjhcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IDRcdWFjMWNcdWM3NTggXHVjNzc4XHVjODExXHVkNTVjIFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgNFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3NDAgXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWQ1NWMgXHVhYzFjXHViOWNjIFx1YzVmNFx1YjlhY1x1YmE3MCwgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NCBcdWJiMzhcdWFjZmMgQlx1YzVkMFx1YzExYyBBXHViODVjIFx1YWMwMFx1YjI5NCBcdWJiMzhcdWM3NDAgXHViY2M0XHVhYzFjXHViODVjIFx1Yzc5MVx1YjNkOVx1ZDU1Y1x1YjJlNC4gXHViYjM4XHViNGU0XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWIyOTQgXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgMVx1YmQ4NFx1YzVkMCBcdWQ1NWMgXHViYzg4IFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgOTBcdWIzYzRcdWM1MjkgXHViYzE0XHViMDEwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZjhcdWI4NWNcdWM1ZDBcdWIyOTQgXHVjZDFkIEtcdWFjMWNcdWM3NTggXHViY2Y0XHViYjNjXHVjMGMxXHVjNzkwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIDFcdWJkODRcdWM1ZDAgXHViYjM4XHVjNzc0IFx1YzVmNFx1YjliMCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OCBcdWM2YzBcdWM5YzFcdWM3NzRcdWFjNzBcdWIwOTggXHVjNmQwXHVkNTU4XHViMjk0IFx1YmMyOVx1ZDVhNVx1Yzc1OCBcdWJiMzhcdWM3NzQgXHVjNWY0XHViOWI0IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWFlMzBcdWIyZTRcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmY4XHViODVjXHVjNWQwXHVjMTFjIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjOGMgXHViNDIwIFx1YzcwNFx1Y2U1OFx1YjI5NCAoMSwgMSlcdWM3NzRcdWJhNzAsIFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWJhYThcdWI0ZTAgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgKE0sIE4pXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHViOTdjIFx1YzgwNFx1YmQ4MCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjM1NFx1Yjc3Y1x1YjNjNCAoTSwgTilcdWM1ZDBcdWIyOTQgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHViYmY4XHViODVjXHViOTdjIFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YmNmNFx1YmIzYyBcdWMwYzFcdWM3OTBcdWI5N2MgXHViYWE4XHVjNTQ0XHVjMTFjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMgXHViYmY4XHViODVjXHViOTdjIFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTSwgTigyICZsZTsgTSwgTiAmbGU7IDEwMClcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTcwLCBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDA4XHVhZTMwXHVjNWQwIFx1YmIzOFx1Yzc3NCBcdWM1ZjRcdWI5YjAgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOLCBFLCBTLCBXXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVhYzAxIFx1YzkwNFx1YzVkMCBOXHVhYzFjXHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWNlNzhcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIChyLCBjKVx1Yjc3Y1x1YmE3NCwgTiwgRSwgUywgV1x1YjI5NCBcdWFjMDFcdWFjMDEgKHIgLSAxLCBjKSwgKHIsIGMgKyAxKSwgKHIgKyAxLCBjKSwgKHIsIGMgLSAxKVx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViYjM4XHVjNzc0IFx1YzVmNFx1YjgyNCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFx1YmNmNFx1YmIzYyBcdWMwYzFcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc4IEsoMSAmbGU7IEsgJmxlOyA4KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmNmNFx1YmIzY1x1YzBjMVx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFIsIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NWMgXHVjZTc4XHVjNWQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzczY1x1YmE3MCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCAoMSwgMSlcdWM3NzRcdWFjNzBcdWIwOTggKE0sIE4pXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NTggJnF1b3Q7MCAwJnF1b3Q7XHVjNzQwIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWM3NDQgXHVjNTRjXHViOWIwXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWJiZjhcdWI4NWNcdWI5N2MgXHVkMGM4XHVjZDljXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC5cclxuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNTU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQW1hemluZyBNYXplIiwiZGVzY3JpcHRpb24iOiI8cD5NYXplIGlzIGEgZ3JpZCBvZiBNeE4gY2VsbHMsIGVhY2ggY2VsbCBoYXMgNCBkb29ycyB0aGF0IGFsbG93IHlvdSB0byBtb3ZlIGludG8gb25lIG9mIHRoZSBuZWlnaGJvdXJpbmcgY2VsbHMuIEF0IGFueSBwb2ludCBvZiB0aW1lIG9ubHkgb25lIG9mIHRoZW0gaXMgb3Blbi4gRG9vcnMgYXJlIG9uZS13YXksIG1lYW5pbmcgdGhhdCBpZiB5b3UgY2FuIG1vdmUgZnJvbSBjZWxsIEEgdG8gQiBpdCBkb2VzIG5vdCBuZWNlc3NhcmlseSBtZWFuIHRoYXQgeW91IGNhbiBtb3ZlIGZyb20gQiB0byBBIGF0IHRoZSBzYW1lIHBvaW50IG9mIHRpbWUuIFRoZSBpbml0aWFsIGFycmFuZ2VtZW50IG9mIGRvb3JzIGlzIGdpdmVuLCBhZnRlciBvbmUgdW5pdCBvZiB0aW1lIGhhcyBwYXNzZWQgdGhlIGN1cnJlbnRseSBvcGVuIGRvb3IgY2xvc2VzIGFuZCB0aGUgb25lIHRoYXQgaXMgOTAgZGVncmVlcyBjbG9ja3dpc2UgZnJvbSBpdCBvcGVucy48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIEsgdHJlYXN1cmUgY2hlc3RzIHRoYXQgeW91IGFyZSBzdXBwb3NlZCB0byBwaWNrIHVwIGFuZCB0aGVpciBjb29yZGluYXRlcyBhcmUgZ2l2ZW4uIFlvdSBjYW4gb25seSBtb3ZlIGZyb20gb25lIGNlbGwgdG8gYW5vdGhlciBpZiB0aGUgY29ycmVzcG9uZGluZyBkb29yIGlzIG9wZW4uIE1vdmluZyBmcm9tIGNlbGwgdG8gY2VsbCB0YWtlcyBvbmUgdW5pdCBvZiB0aW1lLCBidXQgeW91IG1heSBoYXZlIHRvIHdhaXQgZm9yIHRoZSBzcGVjaWZpYyBkb29yIHRvIG9wZW4uPFwvcD5cclxuXHJcbjxwPllvdSBzdGFydCBhdCB0aGUgdG9wIGxlZnQgY29ybmVyICgxLDEpLCBoYXZlIHRvIHBpY2sgdXAgYWxsIHRyZWFzdXJlIGNoZXN0cyBhbmQgZXhpdCB0aGUgbWF6ZSBhdCB0aGUgYm90dG9tIHJpZ2h0IHNxdWFyZSAoTSxOKS4gWW91IGNhbiBlbnRlciB0aGUgc3F1YXJlIChNLE4pIGF0IGFueSB0aW1lLCBidXQgd2lsbCBiZSBhYmxlIHRvIGV4aXQgb25seSBpZiB5b3UgY29sbGVjdGVkIGFsbCB0cmVhc3VyZSBjaGVzdHMuICZxdW90O0V4aXQmcXVvdDsgZG9lcyBub3QgbWVhbiB0aGF0IHlvdSBoYXZlIHRvIGdldCBvZmYgdGhlIGdyaWQsIGp1c3QgdGhhdCB5b3UgYXJlIGF0IChNLE4pIHdpdGggYWxsIHRoZSB0cmVhc3VyZXMuPFwvcD5cclxuXHJcbjxwPldoYXQgaXMgdGhlIG1pbmltdW0gdGltZSB5b3UgbmVlZCB0byBhY2NvbXBsaXNoIHRoaXMgdGFzaz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlNldmVyYWwgdGVzdCBjYXNlcywgZWFjaCBiZWdpbnMgd2l0aCB0d28gaW50ZWdlcnMgb24gYSBsaW5lLCBNIGFuZCBOICgyICZsdDs9IE0sTiAmbHQ7PSAxMDApLiBNIGxpbmVzIGZvbGxvdyB3aXRoIE4gY2hhcmFjdGVycywgZWFjaCBvZiB0aGVtIG9uZSBvZiBOLEUsUyBvciBXLCBpbmRpY2F0aW5nIHRoZSBzaWRlIG9mIHRoZSBjZWxsIHRoYXQgaXMgb3BlbiBhdCB0aW1lIDAuPFwvcD5cclxuXHJcbjxwPklmIHdlIGxhYmVsIGEgY2VsbCBhcyAocixjKSwgTixFLFMsVyBhbGxvdyBtb3ZlbWVudCB0byAoci0xLGMpLChyLGMrMSksKHIrMSxjKSwocixjLTEpIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+TmV4dCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIEsgKDEgJmx0Oz0gSyAmbHQ7PSA4KSwgdGhlIG51bWJlciBvZiBjZWxscyBjb250YWluaW5nIHRyZWFzdXJlIGNoZXN0cy4gSyBsaW5lcyBmb2xsb3cgd2l0aCB0d28gaW50ZWdlcnMgUiBhbmQgQyBvbiBlYWNoLCBkZW5vdGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdHJlYXN1cmUgY2hlc3RzLiBBbGwgSyBsb2NhdGlvbnMgd2lsbCBiZSBkaXN0aW5jdCBhbmQgbm9uZSBvZiB0aGVtIHdpbGwgYmUgYXQgKDEsMSkgb3IgKE0sTikuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgdGhlIGxpbmUgY29udGFpbmluZyB0d28gemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IHRoZSBtaW5pbXVtIHRpbWUgbmVlZGVkIHRvIGV4aXQgdGhlIG1hemUgYWZ0ZXIgY29sbGVjdGluZyBhbGwgdHJlYXN1cmUgY2hlc3RzLCBhcyBkZXNjcmliZWQgaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==