C++ Naive Recursive solution. Naive but clear.


  • 2
    F
    class Solution {
        vector<int> used;
        int min_l, max_l;
        int solve(int f, int len)
        {
            if (len >= max_l)
                return 1;
            used[f] = 1;
            int sum = 0;
            for (int t = 1; t <= 9; ++t)
                if (is_valid(f, t))
                    sum += solve(t, len + 1);
            used[f] = 0;
            if (len >= min_l)
                sum++;
            return sum;
        }
        bool is_valid(int f, int t)
        {
            if (f == t)
                return false;
            if (used[t])
                return false;
            int row_f = (f-1)/3, row_t = (t-1)/3;
            int col_f = (f-1)%3, col_t = (t-1)%3;
            if (row_f == row_t)
            {
                if (abs(col_f - col_t) == 1)
                    return true;
                //if abs(col_f - col_t) == 2
                return used[row_f * 3 + 1 + 1];
            }
            if (abs(row_f - row_t) == 1)
            {
                if (col_f == col_t)
                    return true;
                if (abs(col_f - col_t) == 1)
                    return true;
                //if abs(col_f - col_t) == 2
                return true;//used[row_f * 3 + 1 + 1] && used[row_t * 3 + 1 + 1];
            }
            if (abs(row_f - row_t) == 2)
            {
                if (col_f == col_t)
                    return used[3 + col_f + 1];
                if (abs(col_f - col_t) == 1)
                    return true;//used[3 + col_f + 1] && used[3 + col_t + 1];
                //if abs(col_f - col_t) == 2
                return used[5];
            }
            return false;
        }
    public:
        int numberOfPatterns(int m, int n) {
            used.resize(10);
            min_l = m;
            max_l = n;
            int sum = 0;
            for (int i = 1; i <= 9; ++i)
                sum += solve(i, 1);
            return sum;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.