백준 2186(문자판)

www.acmicpc.net/problem/2186

2186번: 문자판

좀 전형적인 dp문제인것 같다. 

 

그냥 점화식 자체가 그래프 + dp를 하게되면 top-down으로 기저조건 잘 넣고 [][][]이런식으로 몇번째 몇번째 칸을 몇번째 순서로 들어갈지 이런식으로 코드를 짜면 된다.

 

여기서 dp[i][j][num] 에는 마지막에서 (i,j)로 돌아왔을때 경우의 수가 저장된다. 

 

설명이 이상한데 그냥 점화식을 쓰면 

 

dp[i][j][num]  += 모든 num+1의 ni,nj에 대해서 dp[ni][nj][num+1] 이된다. 

 

기저 조건을 잘 넣고 하면 그냥 끝 

 

#include<iostream>
#include<string>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
#define MAX 105

queue<pair<int, int> > q;
string s;
int N, M, K;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int dp[MAX][MAX][MAX];
char mat[MAX][MAX];

int solve(int x, int y, int now) {
	if (now == s.size() - 1)return 1;
	int &ret = dp[x][y][now];
	if (ret!=-1)return ret;
	ret = 0;
	for (int i = 1; i <= K; i++) {
		for (int j = 0; j < 4; j++) {
			int nx = x + i * dx[j];
			int ny = y + i * dy[j];
			if (nx<0 || ny <0 || nx>N || ny > M)continue;
			if (mat[nx][ny] == s.at(now+1)) {
				ret+=solve(nx,ny,now+1);
			}
		}
	}
	return ret;
}

int main() {
	memset(dp, -1, sizeof(dp));
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			char a;
			cin >> a;
			mat[i][j] = a;
		}
	}
	cin >> s;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (mat[i][j] == s.at(0)) {
				q.push(make_pair(i, j));
			}
		}
	}
	int ans = 0;
	while (!q.empty()) {
		pair<int, int> p = q.front();
		q.pop();
		ans+=solve(p.first, p.second, 0);
	}
	cout << ans;

}