351. Android Unlock Patterns

做题历程：

1. 没有独立解出(2016/Jul/07)

本题其实并不难，但是我有点误会了题意，导致我预想的要比实际的问题更加复杂，所以没有做出来。。。
其实本题的核心解法就是用recursive DFS，只不过需要做如下改变：

1. 考虑跨越问题，这个可以用一个2维数组： vector<vector<int>> panel表示，举个栗子，panel[1][3] = 2指1,3隔着2;panel[1][2] = 0指1, 2什么都不隔着
2. 需要注意的是2到9尽管要穿越5， 6；但是算作什么都不隔，所以panel[2][9] = 0
3. 在遍历的时候需要判断：if (visited[i] == false && (panel[cur][i] == 0 || visited[panel[cur][i]] == true)) 这行应该也算这道题的核心代码了

大概需要注意的就这么多，代码如下：

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        vector<vector<int>> panel(10, vector<int>(10, 0));
        panel[1][3] = panel[3][1] = 2;
        panel[1][7] = panel[7][1] = 4;
        panel[3][9] = panel[9][3] = 6;
        panel[7][9] = panel[9][7] = 8;
        panel[1][9] = panel[9][1] = panel[2][8] = panel[8][2] = panel[3][7] = panel[7][3] = panel[4][6] = panel[6][4] = 5;

        vector<bool> visited(10, false);

        int res = 0;
        for (int i = m; i <= n; ++i) {
            res += dfs(panel, 1, i - 1, visited) * 4;
            res += dfs(panel, 5, i - 1, visited);
            res += dfs(panel, 2, i - 1, visited) * 4;
        }
        return res;
    }
private:
    int dfs(const vector<vector<int>>& panel, int cur, int remain, vector<bool>& visited) {
        if (remain < 0) {
            return 0;
        }
        if (remain == 0) {
            return 1;
        }
        visited[cur] = true;

        int tmp_res = 0;

        for (int i = 1; i <= 9; ++i) {
            if (visited[i] == false && (panel[cur][i] == 0 || visited[panel[cur][i]] == true)) {
                tmp_res += dfs(panel, i, remain - 1, visited);
            }
        }

        visited[cur] = false;
        return tmp_res;
    }
};