// 中心对称数问题
// 中心对称数指旋转180°之后和自己完全对称的数
// 能够中心对称的数字包括{{0:0}, {1:1}, {6:9}, {9:6}, {8:8}}
// 给定a，b，求[a,b]之间有多少个中心对称数
// 深度优先搜索，触底返回
#include<iostream>
#include<string>
#include<vector>
using namespace std;

class Solution{
private:
  vector<string> same{"0", "1", "8"};
  vector<pair<char,char>> two{{'0','0'}, {'1','1'}, {'6','9'}, {'9','6'}, {'8','8'}};
  int cnt = 0;
public:
  int strobogrammaticInRange(string low, string high){
    int n1 = low.size();
    int n2 = high.size();
    for (int i=n1;i<=n2;i++){
      DFS(low, high, i, "");
    }
    return cnt;
  }
  void DFS(string& low, string& high, int n, string str){ //n表示一共有几位数
    if (n==0 &&stol(str)>=stol(low) &&stol(str)<=stol(high)) {
      cnt++; cout<<str<<endl;return;
    }
    if (n%2==1) {
      for (auto val:same) DFS(low, high, n-1, val);
    }
    if (n==0||n%2==1) return; // n==0但不满足范围条件，直接返回；n为奇数已经在same里面搜索完了，也返回
    for (int i=(n==2?1:0);i<=4;i++){  //n是偶数，n==2时说明是最外面的两个数，不能是0
      DFS(low, high, n-2, two[i].first+str+two[i].second);
    }

  }
};

int main(){
  Solution s;
  int res = s.strobogrammaticInRange("10","10000");
  // cout<<res;
  return 0;
}