1088

class Solution {
public:
    vector<int> m = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
    vector<int> v = {0, 1, 6, 8, 9};
    int ans = 0;
    int confusingNumberII(int N) {
        for(int n:{1,6,8,9})
            dfs(n, N);
        return ans;
    }

    void dfs(int n, int limit){
        if(n > limit) return;
        if(isConfusing(n))
            ans++;
        if(n > 1e8) return;
        for(int next:v)
            dfs(n*10+next, limit);
    }

    bool isConfusing(int n){
        int num=0, tmp=n;
        while(n){
            int r=n%10;
            n /= 10;
            if(m[r] == -1) return false;
            num = num*10+m[r];
        }
        return (num != tmp);
    }
};