採用活動
～マイナビエンジニアからの挑戦状 vol.2～の解説を公開します！
概要
こんにちは！システム統括本部のS.Dです。
競プロが趣味の私が作成した、オリジナル問題をクリアされた方には、開発エンジニア向けのインターンシップに招待させていただく企画を開催しました。
たくさんのご回答ありがとうございました！！
2021/12/6をもちまして、回答受付は締め切らせていただきました。
本記事では、解説を載せていきたいと思います。
問題
Suzukiさんは、迷路に迷い込みました。
Suzukiさんは、今いる場所から上下左右の4方向に移動することができます。
スタート地点は"S"で与えられ、ゴール地点は"G"で与えられます。
各マスには、壁"■"、通路"."、フラグ("■",".","S","G"以外の文字)があります。
壁は、通ることができませんが、通路もしくはフラグマスは通ることができます。
フラグマスを通ると、フラグを取得します。
Suzukiさんは、最小の移動回数でスタートからゴールまで進みたいです。
また、最短経路のうちで最も少なくフラグマスを通りたいと考えています。
取得したフラグを取得した順番で出力してください。
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■S..■Vwx%[.■A■[ul.[■r^.X■B.a./el!4a..■Jm@N■:Nq.av..■
■.■....w......e■6■.c.■.om?■K..)eV!Q>.rm..■.B.o■v..!■
■"■)?■w.■■.■<ec.■ec>X*+@omr!Rf.Ue■.■Jm.m.■n8U■_av&;■
■.■(.■:kf.kDe.■■.■.q.*pomM.E.<.e■■(.m.5■dy.■■..■..■■
■9■QwM..vW.e■.l...c.....■■■;.■■■$m■m.X.qy■nWx.+■+..■
■.Awb?n.■.e.,l98■cF8d.!om.....o■s■m■(%Ty.n■4■@■■4xc■
■.w<.■)%.e>.lrC^c■-)F.om■Z.!u.■k.J=m.LWMyMnAP..4■.C■
■wWC■.2.e\■l:m.cc...Uom■]i■■me.!...■5■■y]n■,P.*=a■.■
■.■I[:.e0Olq..c,u.■1■m■..;..e■!.:*.m....y■^s.■Oav..■
■^>■..e■.■N■Tc■_>O■om.■■■]■eV!■.'Jm\..Ly.n..■.avVz.■
■.6D■ei.l40+c■..7koms■■(!■!.!.■-imB.(■y■n■5....av2p■
■.$Ae?Vl...c!.Dz■om^■+)e.■a!=_=-mp..Hy"n■<...■av...■
■Fr■..■...c..'%zo■Q.BC$Re.!-.o.m■■.fyAn.R.■.mav.■o■■
■x■l■l■EHc.=7■Fo■V■■5R.e*!■■)vm..`<ykn[\qqX.av■....■
■e.FlfxIc.Q`..omqz.%..e%■bO■.m.$u■yo■.■....■■l%..■i■
■).lpj7c■.D`.omu%.do.e8!5y!Y■'...y.nu`X_&Dav<vA..■■■
■'l.twcq^.■.omh.9■■.em!.■E■■N.■Hy,■;q:!■hav.5...i■■■
■l■I.c■qX■mo■%.!+>De.!■f%.my...y.■Rs>c■■a■>W.x■i...■
■F25c.-e■m_■■.r?."e>!■^?Am...e■5n%.?.m^av■..■.i*<.■■
■D.c).]`Dom■4t..■e*!E■m?mB9'RyEn■%(.n6avs/v.ciD■.!G■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■解説
愚直に全探索を考えてみます。
しかし、単純に全探索することは時間的に不可能に近いです。
というのも、今回は 20×50 マスの迷路なので、左上端から右下端までたどり着く最短経路は
通り存在します。
計算してみると、
33,516,481,089,577,200 通りとなって、全探索することは現実的でないことがわかります。
別の方法を考えてみます。
すべてのマスに関して、"スタート地点から最短何歩で行けるか？" を考えてみることにします。
幅優先探索を行うと各マス高々１回訪れれば最短の歩数は求まります。(最短経路は複数ある場合が多いです）
実際に幅優先探索を行ってみましょう。
#include<bits/stdc++.h>
using namespace std;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int h, w;
cin >> h >> w;
vector<string> m(h);
pair<int,int> s,g;
for(int i = 0; i < h; ++i){
cin >> m[i];
for(int j = 0; j < m[i].size(); ++j) {
if(m[i][j] == 'S') s.first = i, s.second = j;
if(m[i][j] == 'G') g.first = i, g.second = j;
}
}
vector<vector<int>> dist(h, vector<int>(w, 1e9));
queue<pair<int,int>> q;
q.push(s);
dist[s.first][s.second] = 0;
while(!q.empty()) {
pair<int,int> p = q.front();
q.pop();
for(int i = 0; i < 4; ++i){
pair<int,int> next = make_pair(p.first+dy[i], p.second+dx[i]);
if(!(0 <= next.first && next.first < h && 0 <= next.second && next.second < w)) {
continue;
}else if(m[next.first][next.second] != '#' && dist[next.first][next.second] == 1e9){
q.push(next);
dist[next.first][next.second] = dist[p.first][p.second] + 1;
}
}
}
for(int i = 0; i < h; ++i) {
for(int j = 0; j < w; ++j) {
if(m[i][j] != '.') cout << setw(3) << m[i][j];
else cout << setw(3) << dist[i][j];
}
cout << endl;
}
return 0;
}(コードは、壁 ("■") を '#' に変換してから行いました)
S 1 2 ■ V w x % [ 11 ■ A ■ [ u l 18 [ ■ r ^ 25 X ■ B 31 a 33 / e l ! 38 a 40 41 ■ J m @ N ■ : N q 55 a v 58 59
1 ■ 3 4 5 6 w 8 9 10 11 12 13 e ■ 18 ■ 20 c 22 ■ 26 o m ? ■ K 32 33 ) e V ! Q > 40 r m 43 44 ■ 50 B 52 o ■ v 58 59 !
" ■ ) ? ■ w 8 ■ ■ 11 ■ < e c 16 ■ e c > X * + @ o m r ! R f 33 U e ■ 39 ■ J m 43 m 45 ■ n 50 U ■ _ a v & ;
3 ■ ( 6 ■ : k f 11 k D e 15 ■ ■ 20 ■ 22 q 24 * p o m M 30 E 32 < 34 e ■ ■ ( 41 m 43 44 ■ d y 48 ■ ■ 53 54 ■ 58 59 ■
4 ■ Q w M 9 10 v W 13 e ■ 16 l 18 19 20 c 22 23 24 25 26 ■ ■ ■ ; 33 ■ ■ ■ $ m ■ m 43 X 45 q y ■ n W x 52 + ■ + 60 61
5 A w b ? n 11 ■ 13 e 15 , l 18 19 ■ c F 23 d 25 ! o m 29 30 31 32 33 o ■ s ■ m ■ ( % T y 48 n ■ 51 ■ @ ■ ■ 60 x c
6 w < 9 ■ ) % 13 e > 16 l r C ^ c ■ - ) F 26 o m ■ Z 31 ! u 34 ■ k 39 J = m 43 L W M y M n A P 52 53 54 ■ 62 C
w W C ■ 13 12 13 e \ ■ l : m 20 c c 23 24 25 U o m ■ ] i ■ ■ m e 36 ! 38 39 40 ■ 44 ■ ■ y ] n ■ , P 53 * = a ■ 60
8 ■ I [ : 13 e 15 O l q 19 20 c , u 24 ■ 26 ■ m ■ 34 33 ; 33 34 e ■ ! 38 : * 41 m 43 44 45 46 y ■ ^ s 53 ■ O a v 58 59
^ > ■ 12 13 e ■ 16 ■ N ■ T c ■ _ > O ■ o m 29 ■ ■ ■ ] ■ e V ! ■ 39 ' J m \ 44 45 L y 48 n 50 51 ■ 55 a v V z 60
10 11 D ■ e i 16 l 18 19 + c ■ 25 24 25 k o m s ■ ■ ( ! ■ ! 36 ! 38 ■ - i m B 44 ( ■ y ■ n ■ 51 52 53 54 55 a v 58 p
11 $ A e ? V l 18 19 20 c ! 23 D z ■ o m ^ ■ + ) e 36 ■ a ! = _ = - m p 44 45 H y " n ■ < 52 53 54 ■ a v 58 59 60
F r ■ 15 16 ■ 18 19 20 c 22 23 ' % z o ■ Q 30 B C $ R e 36 ! - 39 o 41 m ■ ■ 45 f y A n 50 R 52 ■ 54 m a v 58 ■ o ■
x ■ l ■ l ■ E H c 22 = 24 ■ F o ■ V ■ ■ 32 R 34 e * ! ■ ■ ) v m 43 44 ` < y k n [ \ q q X 55 a v ■ 59 60 61 62
e 15 F l f x I c 22 Q ` 25 26 o m q z 31 % 33 34 e % ■ b O ■ 41 m 43 $ u ■ y o ■ 50 ■ 52 53 54 55 ■ ■ l % 60 61 ■ i
) 16 l p j 20 c ■ 23 D ` 26 o m u % 31 d o 34 e 36 ! 38 y ! Y ■ ' 44 45 46 y 48 n u ` X _ & D a v < v A 61 62 ■ ■
' l 18 t w c q ^ 24 ■ 26 o m h 30 31 ■ ■ 34 e m ! 38 ■ E ■ ■ N 44 ■ H y , ■ ; q : ! ■ h a v 58 59 60 61 62 i ■ ■
l ■ I 20 c ■ q X ■ m o ■ % 30 ! + > D e 36 ! ■ f % 41 m y 44 45 46 y 48 ■ R s > c ■ ■ a ■ > W 60 x ■ i 64 65 66
F 19 20 c 22 - e ■ m _ ■ ■ 30 r ? 33 " e > ! ■ ^ ? A m 43 44 45 e ■ 48 n % 51 ? 53 m ^ a v ■ 59 60 ■ 62 i * < 66 ■
D 20 c ) 23 ] ` D o m ■ 32 t 32 33 ■ e * ! E ■ m ? m B 44 ' R y E n ■ % ( 53 n 55 a v s / v 61 c i D ■ 66 ! G上は、"." の道のみ最短の歩数に書き換えた図です。
確認してみると、7歩目に必ず "w" を踏むように作成されていることがわかります。
同様にして、何歩目に必ず文字を踏む場所があるか確認してみます。
0 does not exist. (S)
7 does not exist. (w)
14 does not exist. (e)
17 does not exist. (l)
21 does not exist. (c)
27 does not exist. (o)
28 does not exist. (m)
35 does not exist. (e)
37 does not exist. (!)
42 does not exist. (m)
47 does not exist. (y)
49 does not exist. (n)
56 does not exist. (a)
57 does not exist. (v)
63 does not exist. (i)
67 does not exist. (!)
68 does not exist. (G)調べてみると、スタートの0歩目とゴールの68歩目を除いて↑の数が存在していないことがわかりました。
また、各歩数で行ける箇所のアルファベットは右に対応していて、実は一通りしか存在していません。
どうやら、上のスタートとゴールを除いた welcome!mynavi! が最短経路のうちで最短の文字列長になりそうです。
しかし、"実際にそのような経路があるか？"を調べなければなりません。
必ずしも、上の文字列だけのフラグマスを通る経路が存在しているとは言えないからです。
S●●■Vwx%[.■A■[ul.[■r^.X■B.a./el!4a..■Jm@N■:Nq.av..
.■●●●●w●●●●●●e■6■.c.■.om?■K..)eV!Q>.rm..■.B.o■v..!
"■)?■w.■■.■<ec.■ec>X*+@omr!Rf.Ue■.■Jm.m.■n8U■_av&;
.■(.■:kf.kDe●■■.■.q.*pomM.E.<.e■■(.m.5■dy.■■..■..■
9■QwM..vW.e■●l●●●c●●●●●■■■;.■■■$m■m.X.qy■nWx.+■+..
.Awb?n.■.e.,l98■cF8d.!om●●●●●o■s■m■(%Ty.n■4■@■■4xc
.w<.■)%.e>.lrC^c■-)F.om■Z.!u●■k.J=m.LWMyMnAP..4■.C
wWC■.2.e\■l:m.cc...Uom■]i■■me●!●●●■5■■y]n■,P.*=a■.
.■I[:.e0Olq..c,u.■1■m■..;..e■!.:*●m●●●●y■^s.■Oav..
^>■..e■.■N■Tc■_>O■om.■■■]■eV!■.'Jm\..Ly●n●●■.avVz.
.6D■ei.l40+c■..7koms■■(!■!.!.■-imB.(■y■n■5●●●●av2p
.$Ae?Vl...c!.Dz■om^■+)e.■a!=_=-mp..Hy"n■<...■av...
Fr■..■...c..'%zo■Q.BC$Re.!-.o.m■■.fyAn.R.■.mav●■o■
x■l■l■EHc.=7■Fo■V■■5R.e*!■■)vm..`<ykn[\qqX.av■●...
e.FlfxIc.Q`..omqz.%..e%■bO■.m.$u■yo■.■....■■l%●.■i
).lpj7c■.D`.omu%.do.e8!5y!Y■'...y.nu`X_&Dav<vA●.■■
'l.twcq^.■.omh.9■■.em!.■E■■N.■Hy,■;q:!■hav.5..●i■■
l■I.c■qX■mo■%.!+>De.!■f%.my...y.■Rs>c■■a■>W.x■i●●.
F25c.-e■m_■■.r?."e>!■^?Am...e■5n%.?.m^av■..■.i*<●■
D.c).]`Dom■4t..■e*!E■m?mB9'RyEn■%(.n6avs/v.ciD■.!G実際に上のような経路で、最短経路で最短の文字列 welcome!mynavi! を得ることができます。
weocome!mynavi! を除いた "●" が実際にたどる経路順です。
最後に
楽しんでいただけたでしょうか？
単純な全探索だけでは解けなくて、実際に試してみる操作が必要でした。
実際の現場の開発でも、実際に試してみることは非常に大切です！
実は、もう少し難しい問題を5,6問用意していたのですが、直前になって難しすぎて問題差し替えになってしまいました泣。
もう少し作問の練習をしようと思います....
次回をお楽しみに！
※本記事は2021年12月時点の内容です。
