<s>[INST] We have a single room that needs to be colored. We are using a constant number of colors so we can represent this as a matrix. A given cell can be colored with any color but two adjacent cells cannot have the same color. The problem is to count the number of ways to color the matrix with a given set of colors such that no two adjacent cells have the same color.

Constraints:
* The number of colors available is C
* The size of the matrix is MxN
* The matrix will contain only single characters representing empty cells that need to be painted. 

Example:

Given the matrix:
.s.
. .
. .

And number of colors as 2, the desired output is 4.

Explanation:
There are 4 ways to color the given matrix with 2 colors:

1)
R G
G R
R G

2)
G R
R G
G R

3)
B G
G B
B G

4)
G B
B G
G B

Note:
Here I have represented colors with characters R for Red and G for Green and B for Blue.

Here is the C++ code for it.

```cpp
#include <iostream>
using namespace std;

int** dp;

int color(int** arr, int** dp,int i, int j, int M, int N, int C) {
    if(i>=M) {
        return 1;
    }
    if(j>=N) {
        return color(arr,dp,i+1,0,M,N,C);
    }
    if(dp[i][j] != -1) {
        return dp[i][j];
    }
    long long ans=0;
    for(int c=0;c<C;c++) {
        bool valid=true;
        // check left
        if(j-1 >=0 && arr[i][j-1]==c) {
            valid=false;
        }
        // check up
        if(i-1>=0 && arr[i-1][j]==c) {
            valid=false;
        }
        // check right
        if(j+1 <N && arr[i][j+1]==c)  {
            valid=false;
        }
        // check down
        if(i+1 <M && arr[i+1][j]==c)  {
            valid=false;
        }

        if(valid) {
            arr[i][j] = c;
            ans+= color(arr,dp,i,j+1,M,N,C);
            arr[i][j] = -1;
        }
    }
    dp[i][j]= ans;
    return ans;
}

int main() {
    int M, N, C;
    cin>>M>>N>>C;
    int** arr = new int*[M];
    for(int i=0;i<M;i++) {
        arr[i] = new int[N];
    }
    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            arr[i][j] = -1;
        }
    }

    dp = new int*[M];
    for(int i=0;i<M;i++) {
        dp[i] = new int[N];
    }
    for(int i=0;i<M;i++) {
        for(int j=0;j<N;j++) {
            dp[i][j] = -1;
        }
    }

    cout<< color(arr,dp,0,0,M,N,C);
    return 0;
}
```
I am getting wrong answer. I feel my algorithm is not correct. Can someone point out my mistake and correct my code?[/INST]