?LeetCode刷題實(shí)戰(zhàn)351：安卓系統(tǒng)手勢(shì)解鎖

class Solution {
  vector<bool> visited;
public:
    int numberOfPatterns(int m, int n) {
      int ans = 0;
      for(int len = m; len <= n; ++len)
      {
        visited = vector<bool> (9, false);
        ans += cal(-1,len);
      }
      return ans;
    }

    bool isok(int idx, int last)
    {
      if(visited[idx]) return false;
      if(last == -1) return true;//第一個(gè)數(shù)
      if((idx+last)%2 == 1) return true;//相鄰的兩個(gè)數(shù)
      int mid = (idx+last)/2;
      if(mid == 4)//對(duì)角線的兩個(gè)端點(diǎn)要連起來
        return visited[mid];//看中點(diǎn)是否占用
      if(idx%3 != last%3 && idx/3 != last/3)
        return true;//不是 同行，或者 同列 的兩個(gè)端點(diǎn)
      return visited[mid];//檢查0,6，中間是3，有沒有被占用
    }
    int cal(int last, int len)
    {
      if(len == 0) return 1;
      int sum = 0;
      for(int i = 0; i < 9; ++i)
      {
        if(isok(i, last))
        {
          visited[i] = true;
          sum += cal(i, len-1);
          visited[i] = false;
        }
      }
      return sum;
    }
};