http://hihocoder.com/contest/mstest2015april2/problem/2

Numeric Keypad

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int key[10][11] = {
	//numbers | avalible number increase sequence 
	{ 1, 0 }, //0
	{ 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },//1
	{ 7, 0,  2, 3,  5, 6, 8, 9 },//2
	{ 3, 3, 6, 9 },//3
	{ 7, 0, 4, 5, 6, 7, 8, 9 },//4
	{ 5, 0, 5, 6, 8, 9 },//5
	{ 2, 6, 9 },//6
	{ 4, 0,  7, 8, 9 },//7
	{ 3, 0,  8, 9 },//8
	{ 1, 9 }//9
};

class KeyBoard{
public:
	int lessOrEqual(int val, int number){
		int *row = key[number];
		int i;
		for (i = row[0]; i > 0; i--){
			if (row[i] <= val)return i;
		}
		return i;
	}

	string val;
	int current = 1;
	bool rec = false;
	int findMax(string& number, int index, int current){
		if (index == number.size()){
			return 0;
		}
		int bit = number[index] - '0';
		int chooseIndex = lessOrEqual(bit, current);
		if (rec){
			chooseIndex = key[current][0];
			rec = false;
		}
		if (chooseIndex == 0){
			rec = true;
			return -1;
		}
		for (int offset = 0; chooseIndex - offset > 0; offset++){
			int choose = key[current][chooseIndex - offset];
			val.push_back('0' + choose);
			if (findMax(number, index + 1, choose) == 0)break;
			val.pop_back();
		}
	}
};

int main()
{
	int testCase = 0;
	cin >> testCase;
	while (testCase--){
		string str;
		cin >> str;
		KeyBoard k;
		k.findMax(str,0,1);
		cout <<k.val  << endl;
	}
	return 0;
}