SRM375 DateFieldCorrection

問題

QWERTYキーボードにおいてキーとキーの距離とは隣接するキーをいくつ隔てて到達できるかによる。ただしスペースキーと隣接するキーとの距離は3と数える。（詳細は問題文中の図）

"month day"という形式で日付が与えられる。この日付はミスタイプされている可能性があるので、この日付に対してもっとも距離の短い正しい表記の日付を返せ。距離が同じ場合はカレンダー上で早いものを返せ。なお文字列と文字列の距離とは同じ位置に現れるキーとキーの距離の和で表されるものとする。

やりかた

キーとキーの距離さえ求まれば、あとは日付を総当りして最小距離の日付にすればいい。
キーとキーとの距離はqwertyキーボードの文字の配列を用意して、隣接するものの距離を1、スペースと隣接する文字との距離を3として持たせてあとは単純なワーシャルフロイドで求まる。

以下ソース。

const int NUM = 38;

int dy[] = {-1, -1, 0, 0, 1, 1};
int dx[] = {0, 1, -1, 1, -1, 0};

string s[4] = {
  "1234567890",
  "qwertyuiop",
  "asdfghjkl?",
  "zxcvbnm???"
};

int d[NUM][NUM];
string mon[] = {
  "January", "February", "March", "April",
  "May", "June", "July", "August",
  "September", "October", "November", "December"
};
int day[] = {
  31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};


class DateFieldCorrection {
public:
  int idx(char a){
    if('0' <= a && a <= '9') return a - '0';
    if('A' <= a && a <= 'Z') return a - 'A' + 10;
    if('a' <= a && a <= 'z') return a - 'a' + 10;
    if(a == ' ') return 36;
    return 37;
  }
  int dist(string a, string b){
    int ret = 0;
    for(int i = 0; i < (int)a.length(); i++)
      ret += d[idx(a[i])][idx(b[i])];
    return ret;
  }
  string correctDate(string input) {
    for(int i = 0; i < NUM; i++)
      for(int j = 0; j < NUM; j++) d[i][j] = INF;
    
    //隣接するキーの距離を1にセット
    for(int i = 0; i < 4; i++){
      for(int j = 0; j < (int)s[i].length(); j++){
	d[idx(s[i][j])][idx(s[i][j])] = 0;
	for(int k = 0; k < 6; k++){
	  int ny = i + dy[k], nx = j + dx[k];
	  if(0 <= ny && ny < 4 && 0 <= nx && nx < s[0].length())
	    d[idx(s[i][j])][idx(s[ny][nx])] = 1;
	}
      }
    }

    //スペースについては隣接するキーとの距離を3にする
    d[idx(' ')][idx('X')] = d[idx('X')][idx(' ')] = 3;
    d[idx(' ')][idx('C')] = d[idx('C')][idx(' ')] = 3;
    d[idx(' ')][idx('V')] = d[idx('V')][idx(' ')] = 3;
    d[idx(' ')][idx('B')] = d[idx('B')][idx(' ')] = 3;
    d[idx(' ')][idx('N')] = d[idx('N')][idx(' ')] = 3;
    d[idx(' ')][idx('M')] = d[idx('M')][idx(' ')] = 3;
    d[idx(' ')][idx(' ')] = d[idx(' ')][idx(' ')] = 0;

    //ワーシャルフロイド
    for(int k = 0; k < NUM - 1; k++)
      for(int i = 0; i < NUM - 1; i++)
	for(int j = 0; j < NUM - 1; j++)
	  d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
    
    //日付で総当り
    string ans;
    int distance = INF;
    for(int i = 0; i < 12; i++){
      for(int j = 1; j <= day[i]; j++){
	string cand = mon[i] + " " + i2s(j);
	if(input.length() != cand.length()) continue;
	if(dist(cand, input) < distance){
	  distance = dist(cand, input);
	  cout << cand << " " << distance << endl;
	  ans = cand;
	}
      }
    }
    return ans;
  }
};