Editorial for 第2回卬高杯 D問題 - Chessroom - Koukouhai

Editorial for 第2回卬高杯 D問題 - Chessroom

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: RenCoda3

ヒント

ヒント1

ナイトの移動の仕方を「このタイルからどのタイルへ移動できるか」に注目して考えると、解法が見えてくるかもしれません。

ヒント2

実はナイトの移動を図形的に表現することができます。
「頂点」は各タイル、「辺」は繋いでいる2つの頂点＝タイルは互いに行き来できるということを表しています。

ヒント3

答えを求めるには、ナイトを初期位置から全てのタイルに最も少ない回数で到着する必要がありますね。
最小の移動回数を求めるためには、どのようにすればいいでしょうか。
そうですね、初期位置から行ける所まで行ってみるのはどうでしょう。そうすれば、何か見えてくるかも。

計算式

初期位置からタイル\((i,j)\) へ移動するために必要な最小の手数を\(m_{(i,j)}\) と表すと、計算式は、\(HW-N+\sum\limits_{k=1}^H\sum\limits_{l=1}^Wm_{(k,l)}\) となります。

Σとは？

和の記号\(\sum\) (「シグマ」と読む)は複数の数を足し合わせた総和を表します。例えば上のような\(\sum\limits_{k=1}^nk\) なら、 1からnまでの全ての整数の和を表しています。詳しくは高校数学(数学Bの「数列」の単元)で学習するので、興味を持った方は調べてみてください。

概説

さて、上記式より、\(\sum\limits_{k=1}^H\sum\limits_{l=1}^Wm_{(k,l)}\) を求める必要があります。しかし、\(m_{(i,j)}\) を1タイルずつ調べようとしても答えは求められますが、最悪\(O((HW)^2)\) ほどの計算量となり、TLE(時間制限超過)してしまう可能性があります。同じタイルを何度も通ってしまっているためです。これを解消すれば、もっと計算量を少なくできそうですね。

そこで、BFS(幅優先探索)というアルゴリズムを用いて、各タイルへ移動するのに必要な最小の手数を求めます。ナイトの動きは重みなしグラフ(辺に長さなどの情報がない、または辺に含まれる情報が全く同じグラフ)とみなして考える事ができ、このアルゴリズムの計算量は\(O(HW)\) であり、\(1≤HW≤1\times10^6\) ですから、実行時間内に十分高速に解くことができます。

※BFS(幅優先探索)とは、題意に沿って簡単に説明すると「あるタイルから移動できるタイルを探し、さらにそのタイルから移動できるタイルを探すことを繰り返す」という手段です。さらに詳しい説明はここでは省きますが、この繰り返しによって各タイルへ移動する最短経路、すなわち最小の手数を求めることができると証明されています。

実装例

BFSを利用した実装例(C++20)


#include <bits/stdc++.h>
using namespace std;

int main() {
  int h, w, x, y, n; cin >> h >> w >> x >> y >> n;

  set<pair<int,int>> s;
  for(int i=0; i<n; i++){
    int a, b; cin >> a >> b;
    s.insert(make_pair(a-1,b-1));
  }

  vector<vector<int>> dist(h,vector<int>(w));
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      dist[i][j]=-1;
    }
  }
  queue<pair<int,int>> todo;
  dist[x-1][y-1]=1;
  for(auto itr=s.begin(); itr!=s.end(); itr++){
    pair<int,int> p=*itr;
    dist[p.first][p.second]=0;
  }
  todo.push(make_pair(x-1,y-1));

  // distは初期位置から何手でそのタイルに旗を置けるかを表す。
  // つまり、dist[i][j]は初期位置(x,y)から
  // タイル(i,j)に旗を置くのに必要な手数。
  // 便宜上、まだ訪れていないタイルを-1,
  // ポーンが置かれているタイルを0とした。

  while(!todo.empty()){ //この部分が幅優先探索(BFS)を用いた解き方となっている。
    pair<int,int> p=todo.front();
    int p1=p.first;
    int p2=p.second;
    todo.pop();

    vector<int> at={2,2,1,1,-1,-1,-2,-2};
    vector<int> bt={-1,1,-2,2,-2,2,-1,1};

    for(int i=0; i<8; i++){
      if(p1+at[i]<0||h<=p1+at[i]||p2+bt[i]<0||w<=p2+bt[i]) continue;
      else{
        if(dist[p1+at[i]][p2+bt[i]]!=-1) continue;
        else{
          dist[p1+at[i]][p2+bt[i]]=dist[p1][p2]+1;
          todo.push(make_pair(p1+at[i],p2+bt[i]));
        }
      }
    }
  }

  int sum=0;
  bool all_visited=true;
//最後に、これで全てのタイルに到達できるかどうかを確認する。
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      sum += dist[i][j];
//distの総和が求める値となる。これを求めるために、ポーンが置かれているタイルを0として扱った(そこに移動する必要も、旗を置く必要もないため)。
      if(dist[i][j]==-1) all_visited=false;
//dist内の値がどれか1つでも-1ならば、到達できないタイルがあるということになる。
    }
  }

  if(all_visited) cout << sum;
  else cout << -1;
}