[[어떤 과학의 인공지능 청소기|problem:CLEANER]]

위의 문제를 풀고 있는데 계속 오답이 뜨네요 ㅠㅠ
오답이 뜨는 이유를 혼자 아무리 고민해도 못 찾겠어서 이렇게 질문글 올립니다 ㅜㅜ

~~~ c++
#include

const int MAX_SIZE = 8;

int N , M;
int dir[4][2] = {-1 , 0 , 0 , 1 , 1 , 0 , 0 , -1};
int iTime[MAX_SIZE * MAX_SIZE][2];
int pos[MAX_SIZE][MAX_SIZE];

int endTime;
int solve(int y , int x , int t)
{
if(y == N && x == M)
return t == endTime;

int ret = 0;
if(pos[y][x] == -1 ||  pos[y][x] == t)
{
    int prev = pos[y][x];
    pos[y][x] = -2;
    if(!iTime[t][0] || (iTime[t][0] == y && iTime[t][1] == x))
    {
        for(int i = 0;i < 4;i++)
        {
            int ny = y + dir[i][0];
            int nx = x + dir[i][1];

            if(pos[ny][nx] != -2)
                ret += solve(ny , nx , t + 1);
        }
    }
    pos[y][x] = prev;
}

return ret;

}

int main(void)
{
int T;
for(scanf("%d" , &T);T--;)
{
scanf("%d %d" , &N , &M);

    endTime = N * M - 1;
    for(int i = 0;i <= endTime;i++)
        iTime[i][0] = iTime[i][1] = 0;

    for(int i = 1;i <= N;i++)
    {
        pos[i][0] = pos[i][M + 1] = -2;
        for(int j = 1;j <= M;j++)
        {
            scanf("%d" , &pos[i][j]);
            int t = pos[i][j];
            if(t != -1)
                iTime[t][0] = i , iTime[t][1] = j;
        }
    }

    for(int i = 1;i <= M;i++)
        pos[0][i] = pos[N + 1][i] = -2;

    printf("%d\n" , !(N & 1) && !(M & 1) ? 0 : solve(1 , 1 , 0));
}
return 0;

}
~~~