Submission #66606

ソースコード

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

206

#pragma GCC optimize("Ofast")
#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:01:32
言語	C++17
状態	Accepted
得点	5
ソースコード長	6127 Byte
最大実行時間	812 ms
最大メモリ使用量	269904 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01.txt	AC	42 ms	5592 KB	1
in02.txt	AC	191 ms	47196 KB	1
in03.txt	AC	93 ms	23080 KB	1
in04.txt	AC	91 ms	21576 KB	1
in05.txt	AC	207 ms	56168 KB	1
in06.txt	AC	562 ms	161624 KB	1
in07.txt	AC	580 ms	161476 KB	1
in08.txt	AC	577 ms	161436 KB	1
in09.txt	AC	563 ms	161392 KB	1
in10.txt	AC	575 ms	161344 KB	1
in11.txt	AC	607 ms	161684 KB	1
in12.txt	AC	608 ms	161664 KB	1
in13.txt	AC	617 ms	161648 KB	1
in14.txt	AC	600 ms	161616 KB	1
in15.txt	AC	606 ms	161720 KB	1
in16.txt	AC	794 ms	269904 KB	1
in17.txt	AC	812 ms	269872 KB	1
in18.txt	AC	224 ms	161384 KB	1
in19.txt	AC	664 ms	164812 KB	1
in20.txt	AC	668 ms	165428 KB	1
in21.txt	AC	437 ms	161432 KB	1
in22.txt	AC	433 ms	161408 KB	1
in23.txt	AC	464 ms	161392 KB	1
in24.txt	AC	16 ms	608 KB	1
sample01.txt	AC	19 ms	564 KB	1
sample02.txt	AC	20 ms	644 KB	1