[VH1731] 텔레포터

• 당신은 번득이는 아이디어로 순간이동을 하는 텔레포터를 순식간에 만들었다.

  
  이 기계는 N행 M열로 이루어진 2차원 격자 모양의 지역을 텔레포터로 그 누구보다 멀리 정확하게 이동한다.

  
  하지만 텔레포터는 해로운 광선을 항상 내뿜는다.

  
  그 광선을 피하기 위해서 텔레포터 할 수 있는 지역이 제한된다.

  
  따라서 텔레포터의 사용법이 따로 존재하는데.

  
  아래의 규칙이 모두 지켜지게 움직여야 한다.

  
  

  1. 상, 하, 좌, 우 중 하나의 방향을 한가지 방향을 정해서 적어도 3칸 이상 이면 어디든 “1차 위치”를 잡을 수 있다.( “1차 위치”는 실제로 이동한 것이 아니다)
  

  2. 앞에서 했던 1번 조건의 방향과 수직인 방향 2가지가 있는데, 둘 중 한 가지 방향으로 적어도 2칸 이상을 “1차 위치”에서 이동하면 갈 수 있다.
  

  3. 지도를 벗어나 움직일 수 없다.

  
  아래 그림은 현재 위치에서 갈 수 있는 지역들을 도식화 한 것이다.

  
  

  A	B	C	D	E	F	G	H	I
  B	C	D	E	F	G	H	I	J
  C	D	E	F	G	H	I	J	K
  D	E	F	G	H	I	J	K	L
  E	F	G	H	I	J	K	L	M
  F	G	H	I	J	K	L	M	N
  G	H	I	J	K	L	M	N	O
  H	I	J	K	L	M	N	O	P
  I	J	K	L	M	N	O	P	Q

  
  

  
  

  
  검정색 칸이 현재 위치일 때에 붉은색 칸이 텔레포터로 갈 수 없는 위치이다. 흰색은 순간이동을 할 수 있는 곳이다.

  
  하지만 정말 텔레포터를 이용해서 어디든 갈 수 있는지 확인해보고 싶었다.

  
  확인할 방법이란, 모든 지역에 알파벳을 새겨 넣어 놓은 다음

  
  텔레포터를 이용해 원하는 알파벳이 적혀있는 지역을 순간이동을 하여 문자열을 만들어 내려고 한다.

  
  만족시킬 수 있는 이동 경로의 경우의 수를 구해보자. 단, 시작하는 위치는 내가 원하는 대로 정할 수 있다.

  
  

  [입력]

  
  첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.

  
  각 테스트 케이스의 첫 번째 줄에는 격자의 행과 열을 나타내는 이 주어진다.

  
  두 번째 줄에는 제시한 문자열이 주어진다. 이 문자열의 길이는 50 이하이다. 세 번째 줄부터 돌에 적혀 있는 알파벳이 N 줄에 걸쳐서 주어진다. 모든 알파벳은 대문자만 사용된다.

  
  

  [출력]

  
  각 테스트 케이스마다 가능한 경우의 수를 로 나눈 나머지를 출력하라.

  
  

  입력 예제
  2 4 3 AC AOC OOO OOO AOC 5 5 ACA BAACC ABABC ABCAA ACACA ACCCB	// 테스트 케이스 개수 // 첫 번째 테스트 케이스, N = 4 M = 3 // 만들어내야 할 문자 // 지도 N*M..       //두 번째 테스트 케이스, N = 5 M = 5

  
  

   
  

  출력 예제
  #1 2 #2 44	// 첫 번째 테스트 케이스 결과 // 두 번째 테스트 케이스 결과

  
  

   

  #include <stdio.h>   int N, M; char B[301][301]; long long dp[51][301][301], s[51][301][301]; int main(const int argc, const char** argv) {     int T, Ti = 1; scanf("%d", &T);     while (T--) {         scanf("%d%d", &N, &M);           char ch, str[51];         scanf("%s", str);         for (int i = 0; i < N; ++i) {             scanf("%s", B + i);         }           int k = 0;         while (ch = str[k]) {             for (int i = 1; i <= N; ++i) {                 for (int j = 1; j <= M; ++j) {                     long long& sum = dp[k][i][j] = 0;                     if (B[i - 1][j - 1] == ch) {                         if (k == 0) {                             sum = 1;                         } else {                             int t = i - 2, b = i + 2, l = j - 2, r = j + 2;                             if (t > 0) {                                 if (l > 0) { sum += s[k - 1][t][l] - dp[k - 1][t][l]; }                                 if (r <= M) { sum += s[k - 1][t][M] - s[k - 1][t][r - 1] - dp[k - 1][t][r]; }                             }                             if (b <= M) {                                 if (l > 0) { sum += s[k - 1][N][l] - s[k - 1][b - 1][l] - dp[k - 1][b][l]; }                                 if (r <= M) { sum += s[k - 1][N][M] - s[k - 1][b - 1][M] - s[k - 1][N][r - 1] + s[k - 1][b - 1][r - 1] - dp[k - 1][b][r]; }                             }                             sum %= 1000000007;                         }                     }                     s[k][i][j] = (dp[k][i][j] + s[k][i - 1][j] + s[k][i][j - 1] -s[k][i - 1][j - 1] + 1000000007) % 1000000007;                 }               }             ++k;         }             printf("#%d %d\n", Ti++, s[k-1][N][M]);     }     return 0; }