結果

問題 No.424 立体迷路
ユーザー uenokuuenoku
提出日時 2016-09-23 00:10:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,093 bytes
コンパイル時間 755 ms
コンパイル使用メモリ 88,408 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-18 16:51:54
合計ジャッジ時間 1,832 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,500 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using namespace std;
typedef long double ld;
typedef long long int lli;
const double eps = 1e-11;
int vex[4] = {1, 0, -1, 0};
int vey[4] = {0, 1, 0, -1};
typedef vector<double> Vec;
typedef vector<int> vec;
typedef vector<Vec> MAT;
typedef vector<vec> mat;
lli MOD = 1000000007;
int used[55][55];
int fed[55][55];
struct P {
    int x, y;
    P(int x, int y) { this->x = x, this->y = y; }
};
int h, w;
bool inrange(int x, int y)
{
    return x >= 0 && x < w && y < h && y >= 0;
}
int main()
{
    int sx, sy, gx, gy;
    cin >> h >> w >> sx >> sy >> gx >> gy;
    queue<P> que;
    que.push(P(sy - 1, sx - 1));
    char c;
    rep(i, h) rep(j, w)
    {
        cin >> c;
        fed[j][i] = c - '0';
    }
    while (!que.empty()) {
        P p = que.front();
        que.pop();
        used[p.x][p.y] = 1;
        rep(i, 4)
        {
            if (inrange(p.x + vex[i], p.y + vey[i]) && abs(fed[p.x][p.y] - fed[p.x + vex[i]][p.y + vey[i]]) <= 1 && !used[p.x + vex[i]][p.y + vey[i]]) {
                que.push(P(p.x + vex[i], p.y + vey[i]));
                used[p.x + vex[i]][p.y + vey[i]] = 1;
            }
            if (inrange(p.x + 2 * vex[i], p.y + 2 * vey[i]) && abs(fed[p.x][p.y] - fed[p.x + 2 * vex[i]][p.y + 2 * vey[i]]) == 0 && fed[p.x][p.y] - fed[p.x + vex[i]][p.y + vey[i]] > 0 && !used[p.x + 2 * vex[i]][p.y + 2 * vey[i]]) {
                que.push(P(p.x + 2 * vex[i], p.y + 2 * vey[i]));
                used[p.x + 2 * vex[i]][p.y + 2 * vey[i]] = 1;
            }
        }
    }
    /*   rep(i, h) rep(j, w)
    {
        cout << used[j][i];
        if (j == w - 1)
            cout << endl;
    }
    */
    cout << (used[gy - 1][gx - 1] ? "YES" : "NO");
    cout << endl;
}
0