Maximum-Cup 2018 B
問題ページ
B: 駆け抜けろ!埼大山車部!! - Maximum-Cup 2018 | AtCoder
考えたこと
- 制約が小さいし全探索
- d[y][x][向き][右折した回数][左折した回数] = (通ったか) としてBFSをする
- 左折がa回、右折がb回なのに逆にしてたり曲がる回数の条件を達成する前にゴールを通過するのをだめだと思ってたりいろいろバグらせ続けて7WA(は?)
- がんばって実装すると通った
AOJICPCの150~200あたりにありそう
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0}; int d[20][20][4][20][20]; string s[20]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int a, b, h, w; cin >> a >> b >> h >> w; REP(i, h) cin >> s[i]; queue<VI> que; que.push({1, 1, 2, 0, 0}); REP(i, 20) REP(j, 20) REP(k, 4) REP(l, 20) REP(i2, 20) { d[i][j][k][l][i2] = INF; } d[1][1][2][0][0] = 0; while(que.size()) { VI v = que.front(); que.pop(); // 直進 int nx = v[1] + dx[v[2]], ny = v[0] + dy[v[2]]; if(s[ny][nx] != '#' && d[ny][nx][v[2]][v[3]][v[4]] == INF) { d[ny][nx][v[2]][v[3]][v[4]] = 0; que.push({ny, nx, v[2], v[3], v[4]}); // cout << "f:" << VI{ny, nx, v[2], v[3], v[4]} << endl; } // 右 int ndir = (v[2]+1)%4; nx = v[1] + dx[ndir], ny = v[0] + dy[ndir]; if(s[ny][nx] != '#' && v[3]+1 <= b && d[ny][nx][ndir][v[3]+1][v[4]] == INF) { d[ny][nx][ndir][v[3]+1][v[4]] = 0; que.push({ny, nx, ndir, v[3]+1, v[4]}); } // 左 ndir = (v[2]+3)%4; nx = v[1] + dx[ndir], ny = v[0] + dy[ndir]; if(s[ny][nx] != '#' && v[4]+1 <= a && d[ny][nx][ndir][v[3]][v[4]+1] == INF) { d[ny][nx][ndir][v[3]][v[4]+1] = 0; que.push({ny, nx, ndir, v[3], v[4]+1}); } } bool flag = false; REP(i, 4) if(d[h-2][w-2][i][b][a] != INF) flag = true; if(flag) cout << "Yes" << endl; else cout << "No" << endl; return 0; }