Submission #66605

ソースコード

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

#include "bits/stdc++.h"
 
// Begin Header {{{
#pragma region
using namespace std;
 
#ifndef DEBUG
#define dump(...)
#endif
 
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i)
#define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
#define let const auto
 
constexpr size_t    operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t  operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };
 
constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;
 
using usize = size_t;
using imax = intmax_t;
using uimax = uintmax_t;
using ld = long double;
 
template <class T, class Compare = less<>>
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template <class T, class Compare = greater<>>
using MinHeap = priority_queue<T, vector<T>, Compare>;
 
inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}
 
template <class Container, class Value = typename Container::value_type,
enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr>
inline istream& operator>>(istream &is, Container &vs) {
    for (auto &v: vs) is >> v;
    return is;
}
 
template <class T, class U>
inline istream& operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
 
inline void output() { cout << "\n"; }
template <class Head, class... Tail>
inline void output(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << " ";
    output(forward<Tail>(tail)...);
}
 
template <class Container, class Value = typename Container::value_type,
enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr>
inline ostream& operator<<(ostream &os, const Container &vs) {
    static constexpr const char *delim[] = {" ", ""};
    for (auto it = begin(vs); it != end(vs); ++it) {
        os << delim[it == begin(vs)] << *it;
    }
    return os;
}
 
template <class Iterator>
inline void join(const Iterator &Begin, const Iterator &End, const string &delim = "\n", const string &last = "\n") {
    for (auto it = Begin; it != End; ++it) {
        cout << ((it == Begin) ? "" : delim) << *it;
    }
    cout << last;
}
 
template <class T>
inline vector<T> makeVector(const T &init_value, size_t sz) {
    return vector<T>(sz, init_value);
}
 
template <class T, class... Args>
inline auto makeVector(const T &init_value, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(init_value, args...))>(sz, makeVector<T>(init_value, args...));
}
 
template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
 
    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};
 
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}
 
template <class Container>
struct reverse_t {
    Container &c;
    reverse_t(Container &c) : c(c) {}
    auto begin() { return c.rbegin(); }
    auto end() { return c.rend(); }
};
 
template <class Container>
auto reversed(Container &c) {
    return reverse_t<Container>(c);
}
 
template <class T>
inline bool chmax(T &a, const T &b) noexcept {
    return b > a && (a = b, true);
}
 
template <class T>
inline bool chmin(T &a, const T &b) noexcept {
    return b < a && (a = b, true);
}
 
template <class T>
inline T diff(const T &a, const T &b) noexcept {
    return a < b ? b - a : a - b;
}
 
void operator|=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs | rhs;
}
 
void operator&=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs & rhs;
}
 
void operator^=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs ^ rhs;
}
 
void ioinit() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
    clog << fixed << setprecision(10);
}
#pragma endregion
// }}} End Header
 
signed main() {
    ioinit();
 
    var(int, H, W);
    var(int, sy, sx, gy, gx);
    sy--, sx--, gy--, gx--;
 
    vector<string> ss(H);
    input(ss);
 
    auto dp = makeVector<imax>(LINF, H, W, 5);
    dp[sy][sx][4] = 0;
 
    deque<tuple<int, int, int>> que; // (y, x, dir)
    que.emplace_front(sy, sx, 4);
 
    constexpr array<int, 8> dy = {0, 1, 0, -1, -1, 1, 1, -1};
    constexpr array<int, 8> dx = {1, 0, -1, 0, 1, 1, -1, -1};
 
    const auto inside = [](int y, int x, int H, int W) {
        return (0 <= y && y < H && 0 <= x && x < W);
    };
 
    while (!que.empty()) {
        let [y, x, cur_dir] = que.front();
        que.pop_front();
        rep(dir, 0, 8) {
            let ny = y + dy[dir];
            let nx = x + dx[dir];
            if (!inside(ny, nx, H, W)) continue;
            if (ss[ny][nx] == '#') continue;
            let nxt_dir = min<int>(dir, 4);
            if (nxt_dir == 4) {
                if (chmin(dp[ny][nx][nxt_dir], dp[y][x][cur_dir] + 1)) que.emplace_back(ny, nx, nxt_dir);
            } else {
                if (cur_dir != nxt_dir) {
                    if (chmin(dp[ny][nx][nxt_dir], dp[y][x][cur_dir] + 1)) que.emplace_back(ny, nx, nxt_dir);
                } else {
                    if (chmin(dp[ny][nx][nxt_dir], dp[y][x][cur_dir])) que.emplace_front(ny, nx, nxt_dir);
                }
            }
        }
    }
 
    let res = *min_element(all(dp[gy][gx]));
    output((res == LINF) ? -1 : res);
    return 0;
}

ステータス

項目	データ
問題	1498 - 竜王
ユーザー名	syoribu
投稿日時	2021-05-08 00:00:49
言語	C++17
状態	Accepted
得点	5
ソースコード長	6096 Byte
最大実行時間	839 ms
最大メモリ使用量	269928 KB

セット

	セット	得点	Cases
1	ALL	5 / 5	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01.txt	AC	40 ms	5592 KB	1
in02.txt	AC	185 ms	47196 KB	1
in03.txt	AC	98 ms	23340 KB	1
in04.txt	AC	86 ms	21444 KB	1
in05.txt	AC	213 ms	56164 KB	1
in06.txt	AC	559 ms	161496 KB	1
in07.txt	AC	592 ms	161352 KB	1
in08.txt	AC	584 ms	161432 KB	1
in09.txt	AC	598 ms	161512 KB	1
in10.txt	AC	578 ms	161468 KB	1
in11.txt	AC	615 ms	161684 KB	1
in12.txt	AC	617 ms	161800 KB	1
in13.txt	AC	640 ms	161660 KB	1
in14.txt	AC	626 ms	161632 KB	1
in15.txt	AC	619 ms	161612 KB	1
in16.txt	AC	839 ms	269928 KB	1
in17.txt	AC	819 ms	269900 KB	1
in18.txt	AC	231 ms	161288 KB	1
in19.txt	AC	666 ms	164720 KB	1
in20.txt	AC	684 ms	165340 KB	1
in21.txt	AC	435 ms	161348 KB	1
in22.txt	AC	441 ms	161328 KB	1
in23.txt	AC	452 ms	161180 KB	1
in24.txt	AC	21 ms	516 KB	1
sample01.txt	AC	23 ms	468 KB	1
sample02.txt	AC	18 ms	544 KB	1