寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #D - テンキー (Tenkey)

JOI 2019/2020 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#D - テンキー (Tenkey)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#D - テンキー (Tenkey)
https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_d
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll vv[10][1000000];
int main(void){
  ll v[10][4]={
    {1,-1,-1,-1},{0,2,4,-1},
    {1,3,5,-1},{2,6,-1,-1},
    {1,5,7,-1},{2,4,6,8},
    {3,5,9,-1},{4,8,-1,-1},
    {5,7,9,-1},{6,8,-1,-1}
  };
  ll m,r;
  cin>>m>>r;
  ll ans,a,b,c,d;
  queue<ll> q1,q2,q3;
  for(ll i=0;i<10;i++){
    for(ll j=0;j<m;j++){
      vv[i][j]=-1;
    }
  }
  vv[0][0]=0;
  q1.push(0);
  q2.push(0);
  q3.push(0);
  while(1){
    ans=q1.front();
    a=q2.front();
    b=q3.front();
    q1.pop();
    q2.pop();
    q3.pop();
    c=(a*10+b)%m;
    if(c==r){
      ans++;
      break;
    }
    if(vv[b][c]==-1){
      vv[b][c]=ans+1;
      q1.push(ans+1);
      q2.push(c);
      q3.push(b);
    }
    for(ll i=0;i<4;i++){
      if(v[b][i]==-1){
        break;
      }
      d=v[b][i];
      if(vv[d][a]==-1){
        vv[d][a]=ans+1;
        q1.push(ans+1);
        q2.push(a);
        q3.push(d);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}