[백준] 10748 Cow Hopscotch

왼쪽 끝에서 오른쪽 끝으로 가려고한다

이 때 가지고있는 값이 달라야하며, 왼쪽 오른쪽 각각 1칸이상 떨어져있어야한다

DP로 풀면된다!

x,y를 대각선부터보면서 갈수있으면 더해가고 오른쪽 끝이라면 return1한다~

소스코드

#include <iostream>
#include <cstring>
using namespace std;
#define ll long long
int arr[111][111],n,m,k;
int d[111][111];
int dx[3] = { 1,1,0 };
int dy[3] = { 0,1,1 };
int mod = 1e9 + 7;
int go(int x, int y) {
    if (x == n - 1 && y == m - 1) return 1;
    int&ret = d[x][y];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = x + 1; i < n; i++) {
        for (int j = y + 1; j < m; j++) {
            if (arr[x][y] != arr[i][j]) {
                ret += go(i, j);
                ret %= mod;
            }
        }
    }
    return ret%mod;
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d %d", &n, &m ,&k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) scanf(" %d", &arr[i][j]);
    }
    printf("%d\n", go(0, 0));
}