노동자 고용하기 timer 1s memory 128MB

최근 농부 창호는 황금과 은이 있는 땅을 구매하였고, 노동자들을 고용하여 보석을 채취하고 자신이 원하는 건물을 건설하고자 한다. 땅은 같은 사이즈의 정사각형 칸으로 나뉘어져 있다. 땅의 정보는 여러행의 문자열로 주어지며 주어진 i번째 행의 j번째 열의 원소는 해당 정사각형 칸에 어떠한 것이 있는지를 뜻한다. 원소가 '.'일 경우에는 해당 위치에 잔디가 있다는 것이고, 'X'의 경우에는 바위가, 그리고 'G'와 'S'의 경우에는 황금과 은이 해당 정사각형 칸에 있다는 것이다. 창호는 특정위치의 칸에 노동자들을 위한 작업장을 건설했는데, 작업장이 있는 위치는 'W'로 표시된다.

한 노동자에게는 정확히 하나의 작업장 칸과, 하나의 황금 칸, 하나의 은 칸이 할당이 된다. 할당된 3개의 칸에는 다른 작업자들이 할당이 되지 못한다, 다시 말해서 두 명 이상의 작업자가 동일한 칸에 할당이 되는 일은 없다는 것이다. 각 노동자는 황금과 은을 자신의 작업장에 운반하게 되며, 효용성을 위해서, 이동 거리가 K미터를 초과하는 경우는 운반을 하지 못하게 한다. 이는 모든 노동자에게 할당된 황금과 은의 거리가 최대 K미터가 되어야 한다는 것이다. 거리는 다음과 같이 측정한다. 각 칸에서부터 노동자는 인접한 상, 하, 좌, 우로 움직일 수 있으며, 이때 한칸당 움직이는 거리는 1미터가 소요된다. 노동자는 잔디가 있는 칸과 자신에게 할당된 작업장과 황금, 은이 있는 칸으로만 이동이 가능하다.

창호는 최대한 많은 노동자를 거느려서 일을 효율적으로 진행하려고 한다. 위의 필요여건을 만족시켰을 때 농부 창호가 고용할 수 있는 최대의 노동자의 수를 구하는 프로그램을 작성하라.