AtCoder が提供しているABC（AtCoder Beginner Contest）088 D問題をC++で解いてみました。ABC088は、2018年2月18日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Grid Repainting（Difficulty : 999）
問題の詳細は、リンク先をご覧ください。
BFSで最短経路を計算することにより解を求めることができます。AtCoder Problems による Difficulty は 999 でした。
解答案
C++ プログラム例（ABC088D）
迷路の最短経路を求めます。迷路の最短経路を求め、その経路上のマスを白で残し、その他のマスを黒に塗ります。黒に塗ることができるマスは、最大で
$H \times W$ – もともと黒いマス – 最短経路で通る白のマス
個となります。
もともと黒いマスの数を、13～20行目で最初にカウントします。最短経路は、キューを使い BFS で求めることができます。少し長いですが、22～44行目は、BFSの定番コードとして使用できます。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int block = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
++block;
}
}
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
queue<pair<int, int>> que;
vector<vector<int>> dist(h, vector<int>(w, -1));
que.push(make_pair(0, 0));
dist[0][0] = 1;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_i = now.first;
int now_j = now.second;
for (int d = 0; d < 4; ++d) {
int next_i = now_i + di[d];
int next_j = now_j + dj[d];
if ((0 <= next_i) && (next_i < h) && (0 <= next_j) &&
(next_j < w) && (dist[next_i][next_j] == -1) &&
(s[next_i][next_j] == '.')) {
que.push(make_pair(next_i, next_j));
dist[next_i][next_j] = dist[now_i][now_j] + 1;
}
}
}
if (dist[h - 1][w - 1] == -1) {
cout << -1 << endl;
} else {
cout << h * w - block - dist[h - 1][w - 1] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
問題文はやや長めですが、典型的な迷路の最短経路を求める問題でした。
引き続き ABC の問題を紹介していきます。
