結果
問題 |
No.323 yuki国
|
ユーザー |
![]() |
提出日時 | 2016-04-19 17:56:55 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 230 ms / 5,000 ms |
コード長 | 2,007 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 166,512 KB |
実行使用メモリ | 13,312 KB |
最終ジャッジ日時 | 2024-06-28 12:30:27 |
合計ジャッジ時間 | 3,894 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; namespace { typedef double real; typedef long long ll; template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; os << "[" << vs[0]; for (int i = 1; i < vs.size(); i++) os << " " << vs[i]; return os << "]"; } template<class T> istream& operator>>(istream& is, vector<T>& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } int H, W; int A, sy, sx; int B, gy, gx; vector<string> F; void input() { cin >> H >> W; cin >> A >> sy >> sx; cin >> B >> gy >> gx; F.clear(); F.resize(H); cin >> F; } const int INF = 1<<28; struct S { int y, x, c; S(int y, int x, int c) : y(y), x(x), c(c) {} }; const int dy[] = {0, -1, 0, 1}; const int dx[] = {-1, 0, 1, 0}; const int MAX_H = 50; const int MAX_W = 50; void solve() { static bool D[MAX_H][MAX_W][4000]; memset(D, 0, sizeof(D)); queue<S> Q; Q.push(S(sy, sx, A)); D[sy][sx][A] = 1; while (not Q.empty()) { S cur = Q.front(); Q.pop(); if (cur.y == gy && cur.x == gx && cur.c == B) { cout << "Yes" << endl; return; } for (int i = 0; i < 4; i++) { int ny = cur.y + dy[i]; int nx = cur.x + dx[i]; if (ny < 0 || ny >= H) continue; if (nx < 0 || nx >= W) continue; int nc = cur.c + (F[ny][nx] == '.' ? -1 : 1); if (nc <= 0) continue; if (nc >= 4000) continue; if (not D[ny][nx][nc]) { D[ny][nx][nc] = 1; Q.push(S(ny, nx, nc)); } } } cout << "No" << endl; } } int main() { input(); solve(); return 0; }