提出詳細
ソースコード
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)
template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x) cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//edit
class Solve {
public:
void solve() {
Int W, H;
cin >> W >> H;
vector<vector<Int>> dist(H + 2, vector<Int>(W + 2, INFl));
vector<vector<bool>> wall(H + 2, vector<bool>(W + 2, true));
Int sh, sw, gh, gw;
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
Int v;
cin >> v;
if (v == 1) {
sh = i;
sw = j;
dist[i][j] = 0;
wall[i][j] = false;
} else if (v == 2) {
gh = i;
gw = j;
wall[i][j] = false;
} else if (v == 0) {
wall[i][j] = false;
}
}
}
queue<pair<int, int>> que;
que.emplace(sh, sw);
while (!que.empty()) {
auto top = que.front();
que.pop();
int h = top.first;
int w = top.second;
int dh[] = {-1, 0, 1, 0};
int dw[] = {0, -1, 0, 1};
for (int k = 0; k < 4; ++k) {
int nh = h + dh[k];
int nw = w + dw[k];
if (!wall[nh][nw]) {
if (dist[nh][nw] == INFl) {
dist[nh][nw] = dist[h][w] + 1;
que.emplace(nh, nw);
}
}
}
}
if (dist[gh][gw] == INFl) {
cout << 0 << endl;
} else {
cout << dist[gh][gw] << endl;
}
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
Int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
cout << "Case #" << i << ":" << endl;
Solve().solve();
}
return 0;
}
提出情報
提出出力結果
テストケース情報