結果
問題 | No.323 yuki国 |
ユーザー |
|
提出日時 | 2019-03-18 13:49:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 391 ms / 5,000 ms |
コード長 | 1,108 bytes |
コンパイル時間 | 636 ms |
コンパイル使用メモリ | 76,488 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-07-18 08:00:39 |
合計ジャッジ時間 | 6,581 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 32 |
ソースコード
#include<iostream>#include<vector>#include<queue>#include<cstring>using namespace std;#define inRange(x,a,b) (a <= x && x < b)int di[8] = {0,0,1,-1,1,1,-1,-1};int dj[8] = {1,-1,0,0,1,-1,1,-1};int main(){int h, w, a, si, sj, b, gi, gj;cin >> h >> w >> a >> si >> sj >> b >> gi >> gj;char mat[h][w];for(int i = 0; i < h*w; i++) cin >> mat[i/w][i%w];bool dp[h][w][3500+1];memset(dp, 0, sizeof(dp));queue<pair<int,pair<int,int>>> q;q.push({a, {si,sj}});while(!q.empty()){auto p = q.front(); q.pop();int i = p.second.first, j = p.second.second, c = p.first;if(dp[i][j][c]) continue;dp[i][j][c] = true;if(c == 0) continue;for(int k = 0; k < 4; k++){int ni = i+di[k], nj = j+dj[k];if(!inRange(ni,0,h) || !inRange(nj,0,w) || c+(mat[ni][nj]=='*'?1:-1) > 3500 || dp[ni][nj][c+(mat[ni][nj]=='*'?1:-1)]){continue;}q.push({c+(mat[ni][nj]=='*'?1:-1), {ni,nj}});}}cout << (dp[gi][gj][b]?"Yes":"No") << endl;return 0;}