AtCoder Beginner Contestの過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - 8 Puzzle on Graph
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #D - 8 Puzzle on Graph https://atcoder.jp/contests/abc224/tasks/abc224_d 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll m; cin>>m; vector<ll> g[10]; ll u,v; for(ll i=1;i<=m;i++){ cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } ll p; string s="999999999"; for(ll i=1;i<=8;i++){ cin>>p; s[p-1]=i+'0'; } queue<string> qs; qs.push(s); map<string,ll> mp; mp[s]=0; while(!qs.empty()){ string t=qs.front(); qs.pop(); for(ll i=1;i<=9;i++){ if(t[i-1]=='9'){ v=i; } } for(auto i : g[v]){ string u=t; swap(u[i-1],u[v-1]); if(mp.count(u)){ continue; } mp[u]=mp[t]+1; qs.push(u); } } if(mp.count("123456789")==0){ cout<<-1<<endl; }else{ cout<<mp["123456789"]<<endl; } return 0; }
AtCoder Beginner Contestは、オンラインジャッジによるプログラミングコンテストです。
日本語と英語に対応していて、週末ごとに実施されているみたいです。
https://practice.contest.atcoder.jp/tutorial
アカウントを登録すれば、誰でも参加できます。