시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViYmY4XHViODVjXHVjNWQwXHVjMTFjIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjOGMgXHViNDIwIFx1YzcwNFx1Y2U1OFx1YjI5NCAoMSwgMSlcdWM3NzRcdWJhNzAsIFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWJhYThcdWI0ZTAgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgKE0sIE4pXHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHViOTdjIFx1YzgwNFx1YmQ4MCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjM1NFx1Yjc3Y1x1YjNjNCAoTSwgTilcdWM1ZDBcdWIyOTQgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHViYmY4XHViODVjXHViOTdjIFx1ZDBjOFx1Y2Q5Y1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHViYWE4XHViNGUwIFx1YmNmNFx1YmIzYyBcdWMwYzFcdWM3OTBcdWI5N2MgXHViYWE4XHVjNTQ0XHVjMTFjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YyBcdWJiZjhcdWI4NWNcdWI5N2MgXHVkMGM4XHVjZDljXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNSBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NDAgXHViNDUwIFx1YzgxNVx1YzIxOCBNLCBOKDIgJmxlOyBNLCBOICZsZTsgMTAwKVx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzAsIFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNkMDhcdWFlMzBcdWM1ZDAgXHViYjM4XHVjNzc0IFx1YzVmNFx1YjliMCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE4sIEUsIFMsIFdcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWFjMDEgXHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1Y2U3OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgKHIsIGMpXHViNzdjXHViYTc0LCBOLCBFLCBTLCBXXHViMjk0IFx1YWMwMVx1YWMwMSAociAtIDEsIGMpLCAociwgYyArIDEpLCAociArIDEsIGMpLCAociwgYyAtIDEpXHViODVjIFx1YWMwMFx1YjI5NCBcdWJiMzhcdWM3NzQgXHVjNWY0XHViODI0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgXHViY2Y0XHViYjNjIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzggSygxICZsZTsgSyAmbGU7IDgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDFcdWM3NTggXHViY2Y0XHViYjNjXHVjMGMxXHVjNzkwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgUiwgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWJjZjRcdWJiM2MgXHVjMGMxXHVjNzkwXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHVjNzNjXHViYTcwIFx1YmNmNFx1YmIzYyBcdWMwYzFcdWM3OTBcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwICgxLCAxKVx1Yzc3NFx1YWM3MFx1YjA5OCAoTSwgTilcdWM3NzggXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1Yzc1OCAmcXVvdDswIDAmcXVvdDtcdWM3NDAgXHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1Yzc0NCBcdWM1NGNcdWI5YjBcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWQwYzhcdWNkOWNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LlxyXG48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE1NTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbWF6aW5nIE1hemUiLCJkZXNjcmlwdGlvbiI6IjxwPk1hemUgaXMgYSBncmlkIG9mIE14TiBjZWxscywgZWFjaCBjZWxsIGhhcyA0IGRvb3JzIHRoYXQgYWxsb3cgeW91IHRvIG1vdmUgaW50byBvbmUgb2YgdGhlIG5laWdoYm91cmluZyBjZWxscy4gQXQgYW55IHBvaW50IG9mIHRpbWUgb25seSBvbmUgb2YgdGhlbSBpcyBvcGVuLiBEb29ycyBhcmUgb25lLXdheSwgbWVhbmluZyB0aGF0IGlmIHlvdSBjYW4gbW92ZSBmcm9tIGNlbGwgQSB0byBCIGl0IGRvZXMgbm90IG5lY2Vzc2FyaWx5IG1lYW4gdGhhdCB5b3UgY2FuIG1vdmUgZnJvbSBCIHRvIEEgYXQgdGhlIHNhbWUgcG9pbnQgb2YgdGltZS4gVGhlIGluaXRpYWwgYXJyYW5nZW1lbnQgb2YgZG9vcnMgaXMgZ2l2ZW4sIGFmdGVyIG9uZSB1bml0IG9mIHRpbWUgaGFzIHBhc3NlZCB0aGUgY3VycmVudGx5IG9wZW4gZG9vciBjbG9zZXMgYW5kIHRoZSBvbmUgdGhhdCBpcyA5MCBkZWdyZWVzIGNsb2Nrd2lzZSBmcm9tIGl0IG9wZW5zLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgSyB0cmVhc3VyZSBjaGVzdHMgdGhhdCB5b3UgYXJlIHN1cHBvc2VkIHRvIHBpY2sgdXAgYW5kIHRoZWlyIGNvb3JkaW5hdGVzIGFyZSBnaXZlbi4gWW91IGNhbiBvbmx5IG1vdmUgZnJvbSBvbmUgY2VsbCB0byBhbm90aGVyIGlmIHRoZSBjb3JyZXNwb25kaW5nIGRvb3IgaXMgb3Blbi4gTW92aW5nIGZyb20gY2VsbCB0byBjZWxsIHRha2VzIG9uZSB1bml0IG9mIHRpbWUsIGJ1dCB5b3UgbWF5IGhhdmUgdG8gd2FpdCBmb3IgdGhlIHNwZWNpZmljIGRvb3IgdG8gb3Blbi48XC9wPlxyXG5cclxuPHA+WW91IHN0YXJ0IGF0IHRoZSB0b3AgbGVmdCBjb3JuZXIgKDEsMSksIGhhdmUgdG8gcGljayB1cCBhbGwgdHJlYXN1cmUgY2hlc3RzIGFuZCBleGl0IHRoZSBtYXplIGF0IHRoZSBib3R0b20gcmlnaHQgc3F1YXJlIChNLE4pLiBZb3UgY2FuIGVudGVyIHRoZSBzcXVhcmUgKE0sTikgYXQgYW55IHRpbWUsIGJ1dCB3aWxsIGJlIGFibGUgdG8gZXhpdCBvbmx5IGlmIHlvdSBjb2xsZWN0ZWQgYWxsIHRyZWFzdXJlIGNoZXN0cy4gJnF1b3Q7RXhpdCZxdW90OyBkb2VzIG5vdCBtZWFuIHRoYXQgeW91IGhhdmUgdG8gZ2V0IG9mZiB0aGUgZ3JpZCwganVzdCB0aGF0IHlvdSBhcmUgYXQgKE0sTikgd2l0aCBhbGwgdGhlIHRyZWFzdXJlcy48XC9wPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbWluaW11bSB0aW1lIHlvdSBuZWVkIHRvIGFjY29tcGxpc2ggdGhpcyB0YXNrPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+U2V2ZXJhbCB0ZXN0IGNhc2VzLCBlYWNoIGJlZ2lucyB3aXRoIHR3byBpbnRlZ2VycyBvbiBhIGxpbmUsIE0gYW5kIE4gKDIgJmx0Oz0gTSxOICZsdDs9IDEwMCkuIE0gbGluZXMgZm9sbG93IHdpdGggTiBjaGFyYWN0ZXJzLCBlYWNoIG9mIHRoZW0gb25lIG9mIE4sRSxTIG9yIFcsIGluZGljYXRpbmcgdGhlIHNpZGUgb2YgdGhlIGNlbGwgdGhhdCBpcyBvcGVuIGF0IHRpbWUgMC48XC9wPlxyXG5cclxuPHA+SWYgd2UgbGFiZWwgYSBjZWxsIGFzIChyLGMpLCBOLEUsUyxXIGFsbG93IG1vdmVtZW50IHRvIChyLTEsYyksKHIsYysxKSwocisxLGMpLChyLGMtMSkgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5OZXh0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgSyAoMSAmbHQ7PSBLICZsdDs9IDgpLCB0aGUgbnVtYmVyIG9mIGNlbGxzIGNvbnRhaW5pbmcgdHJlYXN1cmUgY2hlc3RzLiBLIGxpbmVzIGZvbGxvdyB3aXRoIHR3byBpbnRlZ2VycyBSIGFuZCBDIG9uIGVhY2gsIGRlbm90aW5nIHRoZSBjb29yZGluYXRlcyBvZiB0cmVhc3VyZSBjaGVzdHMuIEFsbCBLIGxvY2F0aW9ucyB3aWxsIGJlIGRpc3RpbmN0IGFuZCBub25lIG9mIHRoZW0gd2lsbCBiZSBhdCAoMSwxKSBvciAoTSxOKS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgY2FzZSBpcyBmb2xsb3dlZCBieSB0aGUgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgdGhlIG1pbmltdW0gdGltZSBuZWVkZWQgdG8gZXhpdCB0aGUgbWF6ZSBhZnRlciBjb2xsZWN0aW5nIGFsbCB0cmVhc3VyZSBjaGVzdHMsIGFzIGRlc2NyaWJlZCBpbiB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d