結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-22 22:55:19 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,088 bytes |
コンパイル時間 | 690 ms |
コンパイル使用メモリ | 91,848 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:04:55 |
合計ジャッジ時間 | 1,390 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <algorithm>#include <utility>#include <functional>#include <cstring>#include <queue>#include <stack>#include <math.h>#include <iterator>#include <vector>#include <string>#include <set>#include <math.h>#include <iostream>#include<map>#include <iomanip>#include <stdlib.h>#include <list>#include <typeinfo>#include <list>#include <set>using namespace std;#define MAX_MOD 1000000007#define REP(i,n) for(int i = 0;i < n;++i)#define LONGINF 1000000000000000000int can_arrive[100][100] = {};int blocks[100][100] = {};int plmi(int a, int b) {if (a == b) {return 1;}if (a == b - 1) {return 1;}if (a == b + 1) {return 1;}return 0;//±1}int main() {int h, w;cin >> h >> w;queue<pair<int, int>> start;int goalx, goaly;REP(i, 1) {int a, b, c, d;cin >> a >> b >> goalx >> goaly;pair<int, int> hoge = make_pair(a, b);start.push(hoge);}can_arrive[start.front().first][start.front().second] = 1;for (int i = 1;i <= h;++i) {string s;cin >> s;for (int q = 1; q <= w;++q) {blocks[i][q] = (int)s[q - 1] - (int)'0';}}while (start.empty() == false) {int x = start.front().first;int y = start.front().second;start.pop();if (x != 1) {if (plmi(blocks[x][y], blocks[x - 1][y]) == true) {if (can_arrive[x - 1][y] == false) {can_arrive[x - 1][y] = true;start.push(make_pair(x - 1, y));}}if (x != 2) {if (blocks[x][y] == blocks[x - 2][y]&&blocks[x][y] > blocks[x-1][y]) {if (can_arrive[x - 2][y] == false) {can_arrive[x - 2][y] = true;start.push(make_pair(x - 2, y));}}}}if (x != h) {if (plmi(blocks[x][y], blocks[x + 1][y]) == true) {if (can_arrive[x + 1][y] == false) {can_arrive[x + 1][y] = true;start.push(make_pair(x + 1, y));}}if (x + 1 != h) {if (blocks[x][y] == blocks[x+2][y]&&blocks[x][y] > blocks[x+1][y]) {if (can_arrive[x+2][y] == false) {can_arrive[x+2][y] = true;start.push(make_pair(x + 2, y));}}}}if (y != 1) {if (plmi(blocks[x][y], blocks[x][y - 1]) == true) {if (can_arrive[x][y - 1] == false) {can_arrive[x][y - 1] = true;start.push(make_pair(x, y - 1));}}if (y != 2) {if (blocks[x][y] == blocks[x][y - 2]&&blocks[x][y] > blocks[x][y-1]) {if (can_arrive[x][y - 2] == false) {can_arrive[x][y - 2] = true;start.push(make_pair(x, y - 2));}}}}if (y != w) {if (plmi(blocks[x][y], blocks[x][y + 1]) == true) {if (can_arrive[x][y + 1] == false) {can_arrive[x][y + 1] = true;start.push(make_pair(x, y + 1));}}if (y + 1 != w) {if (blocks[x][y] == blocks[x][y + 2]&&blocks[x][y] > blocks[x][y+1]) {if (can_arrive[x][y + 2] == false) {can_arrive[x][y + 2] = true;start.push(make_pair(x, y + 2));}}}}}if (can_arrive[goalx][goaly] == true) {cout << "YES" << endl;}else {cout << "NO" << endl;}return 0;}