ICPC 2020-B 接触追跡 解説

問題: https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1641?year=2020

問題の概要

人がm人います．最初，そのうちの一人がウイルスに感染しています．その後，nペアの人が順番に接触します．このとき，感染者と接触した人は感染疑いになります．また，感染疑いの人と接触した場合も感染疑いになります．

最終的に，感染/感染疑いの人は何人いますか？

解法（一般論）

（感染/感染疑いというのがめんどくさいので，以降は単に感染と書くことにします．）

接触者のペアを見たとき，少なくとも片方が感染しているなら両者とも感染します．よって，処理を効率よく行うには，利用者IDから，その人が感染しているかを高速に判定できれば良いです．これは，[利用者ID] = 1(感染) or 0(感染してない)となるような，0と1で構成される配列を使うことで、O(1)でできます．

はじめに，利用者IDがpの人だけ1を代入しておいて，接触者のペアのうち，どちらかの利用者IDの値に1が代入されていれば，両者ともに1を代入することを繰り返します．

最後に，配列の1の数が，そのまま答えになります．配列の要素が0か1であることを考慮すると，これは単に配列の要素の合計値として構いません．

実装（C/C++）

#include <stdio.h>

int main(){
    int m,n,p;
    while(scanf("%d %d %d", &m, &n, &p)){
        if(n+m+p == 0)break;
        // 利用者分の配列を確保して，0で初期化
        int v[100]={0};
        p--; // 0始まりに
        v[p] = 1; // IDがpの人は感染
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d %d", &a, &b);
            a--; b--; // 0始まりに
            // どっちか感染してたら
            if(v[a] == 1 || v[b] == 1){
                // 両方感染する
                v[a] = 1;
                v[b] = 1;
            }
        }
        int ans = 0;
        // 合計を求める
        for(int i=0;i<m;i++){
            ans += v[i];
        }
        printf("%d\n", ans);
    }
}

実装（python）

while True:
    m,n,p = map(int, input().split())
    if n+m+p == 0:
        break
    # 利用者分のリストを確保して，0で初期化
    v = [0 for i in range(m)]
    p -= 1 # 0始まりに
    v[p] = 1 # IDがpの人は感染
    for i in range(n):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        # どっちか感染してたら
        if v[a] == 1 or v[b] == 1:
            # 両方感染
            v[a] = 1
            v[b] = 1
    # 合計を求める
    print(sum(v))

別解: boolのOR演算

これはちょっとトリッキーですが，「どちらか一方でも感染してたら両者とも感染」というのは，OR演算そのものです．いま，感染していることをTrue，感染してないことをFalseとすると，

• 両方感染してるとき，True | True = True
• aだけ感染してるとき，True | False = True
• bだけ感染してるとき，False | True = True
• 両者感染してないとき，False | False = False

となって，感染ルールはOR演算そのものだということが分かります．これを利用すると，各ペアについて，「どちらか一方でも感染している？」ことを気にせずに実装できます．

#include <stdio.h>

int main(){
    int m,n,p;
    while(scanf("%d %d %d", &m, &n, &p)){
        if(n+m+p == 0)break;
        // 利用者分を確保して，falseで初期化
        bool v[100];
        for(int i=0;i<m;i++)v[i] = false;
        p--;
        v[p] = true;
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d %d", &a, &b);
            a--; b--; 
            // お互いに，単に相手とOR演算
            v[a] |= v[b];
            v[b] |= v[a];
            
        }
        int ans = 0;
        // 合計が答え
        for(int i=0;i<m;i++){
            ans += v[i];
        }
        printf("%d\n", ans);
    }
}

ICPC 2020-A カウントダウンアップ2020 解説

問題:

https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1640?year=2020

問題の概要

0から9までの整数で構築された配列があります。この配列の部分列として2,0,2,0はいくつありますか？ ただし、部分列が重なっていても別に数えます。

解法（一般論）

配列の要素を先頭から順に見ていって、そこから先の4要素が2,0,2,0かを判定すれば良いです。

具体的には、i = 0,1,....,n-4に対して、[i]=2, [i+1]=0, [i+2]=2, [i+3]=0かどうかを判定します。これはfor文の中でif文を4つ書いたりして頑張ると書けます。

後述しますが、C++では事前にstring型にしてしまってから.substr()を使う、pythonではリストのスライスを使うことで、処理を簡略化できます。

実装（C/C++）

C言語では、前述した方法をそのまま適用すれば解けます。

#include <stdio.h>

int main(){
    int n;
    while(scanf("%d", &n)){
        if(n==0)break;
        int v[1005];
        // 入力
        for(int i=0;i<n;i++)scanf("%d", &v[i]);
        // 数える変数
        int ans = 0;
        // 判定
        for(int i=0;i<n-3;i++){
            if(v[i]==2 && v[i+1]==0 && v[i+2]==2 && v[i+3]==0){
                ans++;
            }
        }
        // 出力
        printf("%d\n",ans);
    }
}

実装(C++の別解)

C++でも、C言語と同じようにすれば解けます。

別解としては、先に文字列にしてしまって、.substr(idx, len)を使う方法があります。substr(idx, len)は、文字列の添字idxから、len文字だけ切り取ります。例えば、

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s = "abcde";
    // 1番目の文字から2文字切り取る
    string sub = s.substr(1, 2);
    cout<<sub<<endl;
    // "bc"が出力される
} 

です。

これを使うと、以下のように書けます。

#include <iostream>
#include <string>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        int v[1005];
        // 入力
        for(int i=0;i<n;i++)cin>>v[i];
        string s = "";
        // 文字列化
        for(int i=0;i<n;i++){
            s += '0'+v[i];
        }
        int ans = 0;
        // 判定
        for(int i=0;i<n-3;i++){
            // 添字iから4文字切り取る
            if(s.substr(i, 4) == "2020"){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
}

判定は楽になりますが、文字列に直す処理がめんどくさいので、プラマイゼロって感じです。

実装（python）

pythonは、デフォルトで入力を文字列として受け取るので、非常に楽です。一部を切り取るのもスライス[:]でできます。

この場合に気をつけないといけないのは，文字列には空白も含むので，切り取る長さは7文字になることです．また，for文の範囲もnまでではなく，len(文字列)までになることに注意です．（以下のコードでは，スライスが配列外参照しないことを利用して，forの範囲は少しサボっています．）

while True:
    n = int(input())
    if n == 0:
        break
    # 入力
    s = input()
    ans = 0
    # 判定
    for i in range(len(s)):
        # 7文字切り取る
        if s[i:i+7] == "2 0 2 0":
            ans += 1
    print(ans)

もし、整数のリストに直したとしても、スライスで一撃です。

while True:
    n = int(input())
    if n == 0:
        break
    # 入力
    v = list(map(int, input().split()))
    ans = 0
    # 判定
    for i in range(n):
        # 4要素切り取る
        if v[i:i+4] == [2,0,2,0]:
            ans += 1
    print(ans)

A問題みたいに，特に計算量を考えなくて良い場合はpythonのがサクッと書けて良いかもしれない．

【python】xlsxwriterの使い方を丁寧に

はじめに

本記事では，xlsxwriterでエクセルに数値や文字列を書き込む方法を紹介します．また，文字列の一部を色付けする，セルを結合後に書き込む，リスト形式のデータを書き込む，列の幅を調整するようなことも記載しています．

目次

xlsxwriterとは

xlsxwriterは，エクセルファイル（.xlsx）への書き込みをサポートするpythonモジュールです．指定したセルに対して，数値や文字列を書き込むことができます．他にも，一般にエクセルで動作するような式の書き込みもできます．

この記事で紹介する内容を含む公式ドキュメント：

xlsxwriter.readthedocs.io

準備

モジュールのインポート

import xlsxwriter

もしエラーが出る場合は，

pip install xlsxwriter

でモジュールをインストールします．

エクセルファイルの読み込み

.Workbook(ファイル名)でファイルを読み込みます．この後何かしら処理をしますが，最後は必ず.close()で閉じてください．閉じないと，処理が反映されません．

存在しないファイルを開こうとした場合は，自動で新規作成されます．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
# 何かしらの処理
book.close()

シートの指定

エクセルファイルを読み込んだら，.get_worksheet_by_name(シート名)でシートを指定します．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.get_worksheet_by_name('Sheet1')
book.close()

もしシートを新規作成する場合は.add_worksheet()を使います．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
book.close()

値の書き込み

セルの指定方法

数値を書き込むにしろ，文字列を書き込むにしろ，書き込むセルを指定する必要があります．指定方法は2通りあるので，はじめに説明します．

• セル名で指定する方法

  A1やC5などのように，セル名を文字列として与えます．

• 行番号，列番号で指定する方法

  0,0のように，セル名を2つの整数で与えます．最も左上のセルを0,0だと思って，二次元配列のインデックスと思えば良いです．例えば，A1は0,0であり，C5は4,2です．

何でも書き込める.write()

xlsxwriterには，各データ型に対応する書き込みメソッドが定義されています．例えば，数値を書き込むには.write_number()，文字列を書き込むには.write_string()を使います．他にも式やURLに対応するメソッドがあります．そして，これらを統合するようなメソッドとして.write()があります．.write()は引数に対応する書き込みメソッドを呼んでくれるので，実質これだけ使えば事足ります．

以下のサンプルでは，数値，文字列，式を書き込んでいます．セルも2通りで指定しています．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
sheet.write('A1', 5) # 数値．
sheet.write(1, 0, '5') # 文字列．(1,0)=A2
sheet.write(2, 0, "=100+10.5") # 式．(2,0)=A3
book.close()

結果は以下の通りです．同じ5でも，数値と文字列が区別されて書き込まれていることが分かります．また，式も機能していて，計算結果が表示されています．

文字列の一部を装飾する.write_rich_string()

文字列の一部を装飾するには，.write_rich_string()を使います．これにより，太字やイタリック，色付けなどを混ぜて書き込めます．

.write_rich_string()は，書き込みたい文字列をカンマ区切りで3つ以上与えられます．セルの情報を含めない引数が2つ以下の場合や，空文字列を書き込もうとするとエラーになります．（空文字列の書き込みは.write_blank()という専用の関数があるので，.write_blank()，もしくは.write()で書きこむのは問題ありませんが，.write_rich_string()ではサポートしていません．）

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
# カンマ区切りで
sheet.write_rich_string(0, 0, 'bold', 'italic', 'color')
book.close()

ここで，.add_format()を用いて作成したフォーマット変数を，装飾したい文字列の直前に書きます．フォーマット変数は，例えば以下のように作成できます．．

• 太字：bold = book.add_format({'bold': True})

• 斜体：italic = book.add_format({'italic': True})

• 赤字：red = book.add_format({'color': 'red'})

このようにして作られた変数を，装飾したい文字列の直前に書きます．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
bold   = book.add_format({'bold': True})
italic = book.add_format({'italic': True})
red = book.add_format({'color': 'red'})
sheet.write_rich_string(0, 0, 
                        bold, 'bold', 
                        italic, 'italic', 
                        red, 'color')
book.close()

この例では，以下のように装飾が行われます．

フォーマットは他にもあります．以下に簡単な一覧を示します．

目的	.add_format()の中身
太字	{'bold': True}
下線	{'underline': True}
斜体	{'italic': True}
フォント指定	{'font_name': 'フォント名'}
文字サイズ	{'font_size': 整数}
文字色（色名指定）	{'color': 'red'}, {'color': 'blue'}など
文字色（#000000指定）	{'color': '#FF0000'}, {'color': '#0000FF'}など

（上記以外にも指定できます．詳しくはこちら：https://github.com/jmcnamara/XlsxWriter/blob/master/xlsxwriter/format.py）

中央揃えなどを実現するセルのフォーマット

.write_rich_string()では，引数の一番最後にフォーマット変数を与えたとき，それをセルに対するフォーマットだと認識します．例えば，中央揃えにしたいセルがあるとき，

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
center = book.add_format({'align': 'center'})
sheet.write_rich_string(0, 0, 'This is ', 'center ', 'string', center)
book.close()

というように，.write_rich_string()の最後にフォーマット変数を指定します．セルに対するフォーマットは，以下のようなものがあります．

目的	add_format()の中身
（横方向の）中央揃え	{'align': 'center'}
左揃え	{'align': 'left'}
右揃え	{'align': 'right'}
セルの色（色名指定）	{'bg_color': 'red'}
セルの色（#000000指定）	{'bg_color': '#FF0000'}
枠線	{'border': 整数}
（縦方向の）中央揃え	{'valign': 'vcenter'}
文字列を折り返して全体を表示	{'text_wrap': True}

（上記以外にも指定できます．詳しくはこちら：https://github.com/jmcnamara/XlsxWriter/blob/master/xlsxwriter/format.py）

セルを結合して書き込む.merge_range()

特定の範囲のセルを結合して書き込むには，.merge_range()を使います．例えば，A1からC5までを結合して書き込む場合は，

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
sheet.merge_range('A1:C5', 'string') # セルを文字列で指定
# sheet.merge_range(0, 0, 4, 2, 'string') # セルをindexで指定
book.close()

と書けます．セルの情報は文字列でも整数でも指定できます．結合後のセルのフォーマットも指定できます（前述した，引数の一番最後にフォーマット変数を書く方法で）．

リストのデータを特定のセルから行/列方向に書き込む

複数のデータがリストとして存在しているとします．これを特定のセルを始点として書き込む方法です．

行方向に書き込む.write_row()

以下の例では，C2のセルから右方向にデータを書き込みます．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
data = ['A', 'B', 'C']
sheet.write_row('C2', data) # セルを文字列で指定
# sheet.write_row(1, 2, data) # セルをindexで指定
book.close()

列方向に書き込む.write_column()

以下の例では，C2のセルから下方向にデータを書き込みます．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
data = ['A', 'B', 'C']
sheet.write_colmun('C2', data) # セルを文字列で指定
# sheet.write_column(1, 2, data) # セルをindexで指定
book.close()

セルの幅を指定

.set_column()を使用して，特定の範囲のセルの幅を設定できます．以下の例では，A列からC列の幅を20ポイントに設定します．

import xlsxwriter

book = xlsxwriter.Workbook('sample.xlsx')
sheet = book.add_worksheet()
sheet.set_column('A:C', 20) # セルを文字列で指定
# sheet.set_column(0, 2, 20) # セルをindexで指定
book.close()

おわりに

xlsxwriterを用いてエクセルファイルに値を書き込む方法を紹介しました．何かご指摘などありましたら，コメントにお願いいたします．

【Processing】当たり判定を”色”で検出するテクニック

はじめに

Processingによる当たり判定の検出は，座標を用いて行われることがほとんどだと思います．しかし，座標の当たり判定を書くのは結構大変です．大変さの要因として，

• 「当たる側」と「当てられる側」の座標を両方考慮しないといけないこと
• 座標の大小関係を考慮する必要があること

があります．

一方で，色による当たり判定は簡単です．この判定方法の利点は，

• 「当たる側」の座標だけを考慮すれば良いこと
• 座標の大小関係を考慮する必要がないこと

です．一方で，条件式の数が増えがちという欠点はあります．

隙があるので少し自分語りをすると，このテクニックは，僕が学部一年の時に作ったゲームに広く使用しました．一つの適用例として，序盤で挙げさせていただきます（せ，宣伝ではないです）．壁や床を黒で統一し，主人公（の青い四角）との当たり判定を色によって行っています．

https://www.konan-u.ac.jp/faculty/ii/public/prog1/showcase/2017/1/index.html

本記事では，座標の当たり判定をざっとおさらいしつつ，色による当たり判定を紹介します．

目次

まずは座標を使った当たり判定

まずはおさらいも兼ねて，代表的な座標による当たり判定に触れておきましょう．

分かりやすさのため，以下のようなゲーム（のようなもの）を考えます．2つの四角があって，白い四角はマウスで操作できます．また，赤い四角と少しでも重なるとき，Collisionという文字列が上部に表示されます．

int x1,y1,w1,h1,x2,y2,w2,h2;
void setup(){
  size(500, 500);
  textSize(30);
  x1 = y1 = 200;
  w1 = h1 = w2 = h2 = 100;
}

void draw(){
  background(255);
  fill(255, 0, 0);
  rect(x1, y1, w1, h1);
  x2 = mouseX;
  y2 = mouseY;
  fill(255);
  rect(x2, y2, w2, h2);
  if(rect_collision_with_pos(x1, y1, w1, h1, x2, y2, w2, h2)){
    fill(0);
    text("Coliision", 200, 100);
  }
}

boolean rect_collision_with_pos(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2){
  return(x2 <= x1+w1 && 
         x1 <= x2+w2 && 
         y2 <= y1+h1 && 
         y1 <= y2+h2);
}

当たり判定は以下の関数が担っています．

boolean rect_collision_with_pos(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2){
  return(x2 <= x1+w1 && 
         x1 <= x2+w2 && 
         y2 <= y1+h1 && 
         y1 <= y2+h2);
}

この関数では，四角形と四角形の当たり判定を実現していますが，条件式が複雑です．慣れたらすぐに書けるのですが，変数名や不等号の向きを間違えるリスクが高いです．

色による当たり判定

次に色による当たり判定を紹介します．その前に，色を扱うためのメソッドを一つ紹介します．

get()メソッド

get()メソッドは，指定した座標の色を取得します．

get(x座標, y座標)

返り値はcolor型です．

例えば，

// マウスの座標が赤の時に何かしたい
if(get(mouseX, mouseY) == color(255,0,0)){
  // 処理
}

のように使えます．

実装

先ほどの例において，当たり判定の関数を書き換えてみます．

int x1,y1,w1,h1,x2,y2,w2,h2;
void setup(){
  size(500, 500);
  textSize(30);
  x1 = y1 = 200;
  w1 = h1 = w2 = h2 = 100;
}

void draw(){
  background(255);
  fill(255, 0, 0);
  rect(x1, y1, w1, h1);
  x2 = mouseX;
  y2 = mouseY;
  fill(255);
  rect(x2, y2, w2, h2);
  if(rect_collision_with_color(x2, y2, w2, h2)){
    fill(0);
    text("Coliision", 200, 100);
  }
}

boolean rect_collision_with_color(int x, int y, int w, int h){
  color red = color(255, 0, 0);
  int eps = 1;
  return(get(x-eps, y-eps) == red || // 左上の頂点の色
         get(x-eps, y+h+eps) == red || // 左下の頂点の色
         get(x+w+eps, y-eps) == red || // 右上の頂点の色
         get(x+w+eps, y+h+eps) == red); // 右下の頂点の色
}

この例では，以下に青色の点で示した座標の色を見て，当たり判定を検出します．頂点の座標は四角の枠線に重なるので，枠線の色を見てしまわないように，epsという変数を使って外側に1ピクセルずらしています．

実行すると，座標の時とほぼ同じように当たり判定が検出できることが分かります．

ただし，自分より小さい物体の検出が苦手という欠点があります．例えば，辺の真ん中に小さい物体が突っ込んでくるようなことを考えると，4つの頂点を見るだけでは検出できません．

このような場合に備えるために，色を見る座標を増やしてみます．例えば，辺の真ん中も見るようにしましょう．

boolean rect_collision_with_color(int x, int y, int w, int h){
  color red = color(255, 0, 0);
  int eps = 1;
  return(get(x-eps, y-eps) == red || // 左上の頂点の色
         get(x-eps, y+h+eps) == red || // 左下の頂点の色
         get(x+w+eps, y-eps) == red || // 右上の頂点の色
         get(x+w+eps, y+h+eps) == red || // 右下の頂点の色
         get(x+w/2, y-eps) == red || // 上の辺の真ん中
         get(x+w+eps, y+h/2) == red || // 右の辺の真ん中
         get(x+w/2, y+h+eps) == red || // 下の辺の真ん中
         get(x-eps, y+h/2) == red); // 左の辺の真ん中
}

この例では，以下の8点を見ていることになります．

ここまですれば，ほとんどの場合に対応できるでしょう．座標での当たり判定よりも条件式の数は増えますが，一つ一つの条件式はずっと簡単に書けます．座標の大小を考慮する必要はありませんし，ある一つの物体の座標だけを考えれば実装できます．この点をどこまで細かく設定するかは，求める当たり判定の精度や，対象とする物体の大きさによります．場合によっては，辺の1/4地点も必要になるかもしれません．

実用例：床に着地させる

せっかくなので，より実用的な例を一つ載せたいと思います．

アクション系のゲームで，ある床があって，そこに着地させたいことがあると思います．仮にキャラの当たり判定領域を四角形だとして，床の色が黒だとすると，四角形と黒色の当たり判定として書けます．

int x, y, w, h;
void setup(){
  size(500, 500);
  textSize(30);
  x = 100;
  y = 0;
  w = h = 100;
}

void draw(){
  background(255);
  fill(0);
  rect(0, 400, width, 100); // 床のつもり
  fill(255);
  rect(x, y, w, h);
  // 当たり判定が検出されない間，落ち続ける
  if(!rect_collision_with_color(x, y, w, h)){
    y += 5; // 重力のつもり
  }
}

boolean rect_collision_with_color(int x, int y, int w, int h){
  color black = color(0, 0, 0);
  int eps = 1;
  return(get(x-eps, y-eps) == black || // 左上の頂点の色
         get(x-eps, y+h+eps) == black || // 左下の頂点の色
         get(x+w+eps, y-eps) == black || // 右上の頂点の色
         get(x+w+eps, y+h+eps) == black || // 右下の頂点の色
         get(x+w/2, y-eps) == black || // 上の辺の真ん中
         get(x+w+eps, y+h/2) == black || // 右の辺の真ん中
         get(x+w/2, y+h+eps) == black || // 下の辺の真ん中
         get(x-eps, y+h/2) == black); // 左の辺の真ん中
}

当たり判定が検出されない間落ち続けて，検出されると止まれば良いので，if分には当たり判定の関数を否定するものを入れます．中の処理にy座標を足すことを書けば，床への着地が実現できます．

他の図形への応用

本記事では，四角形同士の当たり判定を扱いましたが，おそらく，他の図形でもできると思います．結局，色を見たい点をいくつか置いて，当たり判定の輪郭を作るようなイメージ（Unityでいうコライダー的なもの）なので，複雑な図形同士でもできると思います．

おわりに

本記事では，当たり判定を色で検出する話を書きました．うまく使えば，表現の幅を簡単に広げられる気がするので，ぜひ試してみてください．

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

問題: https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1633

C++で解説しています．

問題の言い換え

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

解法

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

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

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

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

もう少し細かいところを書きます．まず，キーボードの情報を格納する型についてです．この情報は，個のchar型変数だと思っても良いですが，個のstringだと思っても差し支えないです（各文字列の文字数が）．つまり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;
    }
    
}

ICPC 2019 国内予選A 「期末試験の成績」 解説

問題: https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1632

C++で解説しています．

問題の言い換え

整数が行列で並んでいる．列の合計値の最大値を求めよ．

解法

各列の合計を計算して，最大値を出力します．計算方法はいくらでもありますが，二次元配列の舐め方を考慮して2通り紹介します．

二次元配列を横に舐める方法

横に舐めるので，入力と同じようにfor文を回して処理します．列を逐次的に処理できないので，列の合計値を保存する配列を作る必要があります．

max_element()は配列の最大値を求める関数です．（#include <algorithm>が必要）

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n,m;
    while(cin >> n >> m){
        if(n+m == 0)break;
        vector<vector<int>> v(m, vector<int>(n, 0));
        vector<int> col_sum(n, 0);
        // 入力
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin >> v[i][j];
            }
        }
        // 列の合計値を計算
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                col_sum[j] += v[i][j];
            }
        }
        // 最大値を出力
        cout << *max_element(col_sum.begin(), col_sum.end()) << endl;
    }
}

二次元配列を縦に舐める方法

この方法では列を逐次的に処理できるため，列の合計値を保存する配列が必要ありません．単に前の列から合計を計算して，答えの変数を更新します．

この場合，二次元配列を「縦方向に舐める」感覚が必要になります．C/C++において二次元配列の入力を受けるときには，

for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
        // [i][j]で参照

のようにするのが一般的ですが，これは二次元配列を横方向に舐めています．ある行を固定して，列を回します．

一方で，縦方向に回すときには，列を固定して行を回します．コードで言うと，

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        // [j][i]で参照

みたいな感じです（もちろん，この実装は一例です）．

以上を踏まえると，以下のように書けます．

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n,m;
    while(cin >> n >> m){
        if(n+m == 0)break;
        vector<vector<int>> v(m, vector<int>(n, 0));
        // 入力
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin >> v[i][j];
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            int score = 0; // i列目の合計が入る
            for(int j=0;j<m;j++){
                score += v[j][i];
            }
            // 最大値を更新
            ans = max(ans, score);
        }
        cout << ans << endl;
    }
}

ICPC 2003国内予選B 「Get Many Persimmon Trees」

問題URL: https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1125?year=2003

問題の言い換え

横，縦個のマス目がある．ここに個の点を打つ．個目の点は座標である．点の座標は重複しない．この下で，横，縦の領域で囲める点の数の最大値を出力せよ．

解法

まずは点の情報を保存します．これは0で初期化されたの二次元配列に対して，の要素を+1することで得られます．例えば，サンプルの最初のデータセットでは

0 0 0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 1 0 1 0 0
0 1 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 1 0 0 0

のような二次元配列を構築します．16なので，1も16個あります．

次に，答えの最大値をどう探索するかを考えます．とりあえず，横，縦の領域の点の数を求めることを考えると，2重ループでできることが分かります．

for(int i=0;i<T;i++){
 for(int j=0;j<S;j++){
   // 二次元配列[i][j]の 1 or 0 を見る
 }
}

ただし，横，縦の領域は様々に取れるので，これは全通り見てやる必要があります．よって今回は，領域の左上の座標を全探索することにします．4乗オーダーになりますが，が100以下であることを考慮すると，十分高速です．

for(int y=0;y<h-t+1;y++){ // 左上のy座標
  for(int x=0;x<w-s+1;x++){ // 左上のx座標
    for(int i=0;i<T;i++){
      for(int j=0;j<S;j++){
        // 二次元配列[y+i][x+j]の 1 or 0 を見る
      }
    }
  }
}

左上の座標によっては範囲がをはみ出すこともあり得ますが，そのような場合は考慮しなくて良いです．（はみ出したときの点の数は，はみ出さないように調整したときの点の数には勝てないため）

以上を考慮すると，全体としては次のように書けます.

#include <iostream>
#include <vector>

using namespace std;
int main(){
    int n;
    while(cin >> n){
        if(n == 0)break;
        int w, h;
        cin >> w >> h;
        vector<vector<int>> v(h, vector<int>(w, 0));
        # 点を打つ
        for(int i=0;i<n;i++){
            int x, y;
            cin >> x >> y;
            x--; y--;
            v[y][x]++;
        }
        int s, t;
        cin >> s >> t;
        int ans = 0;
        # 左上の座標を全探索
        for(int y=0;y<h-t+1;y++){
            for(int x=0;x<w-s+1;x++){
                # S,Tの領域の点の数を数える
                int count = 0;
                for(int i=0;i<t;i++){
                    for(int j=0;j<s;j++){
                        count += v[y+i][x+j];
                    }
                }
                # 最大値を更新
                ans = max(ans, count);
            }
        }
        cout << ans << endl;
    }
}