class Solution {
public:
    int vis[3][3];
    int ans[10];
    int dir[16][2] = {       //16个方向
        { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 },
        { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 },
        {-2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 },
        { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 }
    };
    void dfs(int x, int y, int t)
    {
        if (9 == t)
        {
            return;
        }
        ans[t++]++;
        vis[x][y] = 1;
        for (int i = 0; i < 16; i++)
        {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (0 <= dx && dx < 3 && dy >= 0 && dy < 3 && vis[dx][dy] == 0)
            {
                dfs(dx, dy, t);
            }
            //如果前8个方向都走过了，可以沿着当前方向在走一步
            else if (i < 8)
            {
                dx = dx + dir[i][0];
                dy = dy + dir[i][1];
                if (0 <= dx && dx < 3 && dy >= 0 && dy < 3 && vis[dx][dy] == 0)
                {
                    dfs(dx, dy, t);
                }
            }
        }
        vis[x][y] = 0;
        return;
    }
    int solution(int m, int n) {
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                memset(vis, 0, sizeof(vis));
                dfs(i, j, 1);
            }
        }
        int num = 0;
        if (m > n)
            return 0;
        else {
            if (n > 9)
                n = 9;
            ans[9] = ans[8];
            for (int i = m; i <= n; i++) {
                num = num + ans[i];
            }
            return num;
        }


    }
};