가장 좋은 자리
시간 제한10초메모리 제한256 MB
각 설계도를 격자에 올려 일치 칸이 가장 많은 위치를 찾고 행과 열이 작은 순으로 동점을 깨 곡물과 가축 수를 출력합니다.
문제
한 농부가 넓은 밭에 새 농장을 지으려고 한다. 밭은 행 열 격자이고, 각 칸에서는 곡물(G)과 가축(L) 중 한 가지 먹거리를 생산한다. 다음은 , 인 밭이다.
12345678
1 GLGGLGLG
2 GGLGGLGL
3 GGLLLGGG
4 LLGLLGLG
5 LGGGLGLL
농부에게는 설계도도 있다. 설계도는 행 열 격자이며 , 이다. 설계도의 각 칸에는 농부가 그 자리에서 얻고 싶은 먹거리인 곡물(G) 또는 가축(L)이 적혀 있다. 다음은 , 인 설계도이다.
123
1 GLL
2 LGG
농부는 설계도를 밭 위에 얹어 농장을 짓는다. 놓는 자리는 왼쪽 위 모서리의 좌표 로 나타내고, 이때 설계도는 밭의 행부터 행까지, 열부터 열까지를 덮는다. 설계도 전체가 밭 안에 들어가야 하므로 이고 이다. , 에 대해 밭의 칸에 있는 먹거리가 설계도의 칸에 적힌 먹거리와 같으면 그 칸에서 먹거리를 생산한다.
농부는 곡물과 가축을 합한 생산량이 가장 많은 자리를 고르려고 한다. 생산량이 같은 자리가 여럿이면 이 가장 작은 자리를 고르고, 그래도 여럿이면 가 가장 작은 자리를 고른다.
위의 밭과 설계도에서 가장 좋은 자리는 이다. 설계도는 1행부터 2행까지, 3열부터 5열까지를 덮고, 그 자리의 밭은 위가 GGL, 아래가 LGG이다. 설계도의 첫 줄 GLL은 첫째 칸과 셋째 칸이 밭과 같아 곡물 1개와 가축 1개를 생산한다. 둘째 줄 LGG는 세 칸이 모두 같아 곡물 2개와 가축 1개를 생산한다. 그래서 이 자리는 곡물 3개와 가축 2개, 모두 5개를 생산한다. 와 에 지어도 5개를 생산하지만 이 행 번호가 더 작고, 나머지 자리는 모두 5개보다 적게 생산한다.
입력
입력에는 밭이 하나 주어진다. 첫째 줄에 두 정수 과 가 주어진다. () 다음 개 줄에는 각각 개의 문자가 주어지며, 밭의 한 행을 나타낸다.
그다음 줄에는 농부가 가진 설계도의 개수 가 주어진다. () 이어서 설계도 개가 주어진다. 각 설계도는 두 정수 와 가 적힌 줄로 시작하고 (, ), 그 뒤에 각각 개의 문자로 이루어진 개 줄이 온다.
밭과 설계도의 모든 문자는 G 또는 L이다.
출력
설계도마다 입력에 주어진 순서대로 한 줄씩 출력한다. 번째 설계도에 대해서는 (는 1부터 센다) Case #X: 를 출력한 다음, 공백 하나로 구분한 네 정수를 출력한다. 앞의 두 정수는 농장을 짓기 가장 좋은 자리의 행 번호와 열 번호이고, 뒤의 두 정수는 그 자리에서 생산하는 곡물의 개수와 가축의 개수다.