問題の言い換え

$h\times w$ のマス目があり，各マスに文字が割り当てられている．最も左上のマスを(0, 0)とする．あなたは(0, 0)におり，1回の移動で上下左右の1マスしか移動できない．いま，ある文字列が与えられる．あなたは文字列の先頭の文字から順に，その文字が書かれたマス目に移動しなければならない．文字列の最後の文字に移動し終わったとき，（移動したマス目の総数）＋（文字数）を求めよ．

解法

問題の言い換えは少々飛躍&雑ですが...

キーボードという設定ですが，マス目の上に文字が乗っていると考えて問題ありません．また，リモコンの説明が色々ありますが，結局，上下左右1マスにしか移動できないということです．

全ての文字についてOKボタンは押さないといけないので，一旦OKボタンは無視して計算して，最後に文字数を足します．（OKボタンは必ず文字数だけ押されるので．）

大まかな実装としては，事前に[文字] = (x, y)となるような辞書を構築しておいて，今いる座標と次の文字の座標とのマンハッタン距離を足していくようなものが簡単だと思います．辞書は，pythonならdict()，C++ならmapやunordered_mapに相当します．また，マンハッタン距離は，x方向の差分とy方向の差分を単に足したものです．

もう少し細かいところを書きます．まず，キーボードの情報を格納する型についてです．この情報は， $h\times w$ 個のchar型変数だと思っても良いですが， $h$ 個のstringだと思っても差し支えないです（各文字列の文字数が $w$ ）．つまりvector<vector<char>>かvector<string>かということですが，後者の方が分かりやすいと思います．それから，(x, y)のような座標の情報は，int型変数を2つ持つ構造体で表現するか，#include <utility>で使えるpair<int,int>で表現すると良いと思います．

これらを踏まえると，以下のようなコードになります．

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <utility>
using namespace std;

int main(){
    int h,w;
    while(cin >> h >> w){
        if(h+w == 0)break;
        vector<string> chars(h);
        for(int i=0;i<h;i++){
            cin >> chars[i];
        }
        // [文字] = 座標の辞書 
        unordered_map<int, pair<int,int>> char2point;
        // 辞書を構築
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                char2point[chars[i][j]] = pair<int,int>(i, j);
            }
        }
        // 文字列を先頭から見ていき，移動したマスを数える．
        string s;
        cin >> s;
        int ans = 0;
        pair<int,int> now_point = pair<int,int>(0, 0);
        for(int i=0;i<s.size();i++){
            pair<int,int> point = char2point[s[i]];
            ans += abs(now_point.first - point.first);
            ans += abs(now_point.second - point.second);
            now_point = point; // 座標を更新
        }
        cout << ans + s.size() << endl;
    }
    
}

gotutiyan’s blog

ICPC 2019 国内予選B 「スクリーンキーボード」解説

問題の言い換え

解法