CFgym：Good morning!（dfs）

For an example input:

3

180

83

132

a possible correct answer is:

180

80

133

题意：如图键盘，只能向下或向右或原地按，T组数据，给出N，1<=N<=200，输出能按出来的离N最近的数字。

思路：dfs构造所有数字存下，二分搜索即可。

# include <bits/stdc++.h>
using namespace std;
int m[6][6]={{-1,-1,-1,-1},{-1,1,2,3},{-1,4,5,6},{-1,7,8,9},{-1,-1,0,-1}};
int dx[2]={0,1}, dy[2]={1,0};
set<int>s;
void dfs(int px, int py, int x, int y, int num)
{
    if(num>=300 || x>4||y>3||m[x][y]==-1)
    {
        if(px==4&&py==2 || px==3&&py==3) s.insert(num);
        return;
    }
    for(int i=0; i<2; ++i)
    {
        int mx = x+dx[i], my = y+dy[i];
        dfs(x, y, mx, my, num);
        if(num < 100)
        {
            dfs(x, y, mx, my, num*10+m[x][y]);
            if(num < 10)
            {
                dfs(x, y, mx, my, (num*10+m[x][y])*10+m[x][y]);
                if(num == 0)
                    dfs(x, y, mx, my, ((num*10+m[x][y])*10+m[x][y])*10+m[x][y]);
            }
        }
    }
}
int main()
{
    dfs(0, 0, 1, 1, 0);
    int t, n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        auto it = s.upper_bound(n);
        int ans = *it;
        if(it != s.begin())
        {
            int tmp = abs(*(--it)-n);
            if(tmp < abs(ans-n)) ans = *it;
        }
        printf("%d\n",ans);
    }
    return 0;
}