結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-22 23:01:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 4,588 bytes |
コンパイル時間 | 671 ms |
コンパイル使用メモリ | 74,932 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:05:39 |
合計ジャッジ時間 | 1,303 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#define NDEBUG#undef __STRICT_ANSI__#include <string>#include <cstdlib>#include <cstdio>#include <tuple>#include <vector>#include <set>#include <algorithm>#include <functional>#include <cstring>#include <cmath>#include <cfloat>#include <cassert>using namespace std;#undef assert#define assert(e)#include <cstdarg>#include <sys/time.h>class XsRandom {unsigned long long a;unsigned long long b;public:inline XsRandom() : a(0x8a5cd789635d2dffULL), b(0x121fd2155c472f96ULL) {}inline XsRandom(const XsRandom & o) : a(o.a), b(o.b) {}inline unsigned long long next64() {unsigned long long c = a ^ (a<<23);a = b;b = c ^ a ^ (c>>18) ^ (a>>5);return b + a;}inline XsRandom(unsigned int seed) : a(0x8a5cd789635d2dffULL), b(0x121fd2155c472f96ULL) {seed = seed * 1234567891 + 521288629;unsigned long long a2 = a;unsigned long long b2 = b;while(seed) {next64();if(seed & 1) {a2 ^= a;b2 ^= b;}seed >>= 1;}a = a2;b = b2;}inline unsigned int next() {return (unsigned int)next64();}inline int nextInt(int r) {assert(1<=r);return ((unsigned long long)next() * r)>>32;}};typedef XsRandom MyRandom;MyRandom g_myRand;double g_startTime;double g_suspendTime = 0;const double g_timeupSecBase = 9.8;double g_timeupSec = g_timeupSecBase;#include <numeric>const char * nextCLineOrWord(int mode) {static char buf[65536];static int bufLen = sizeof(buf);static int bufPos = sizeof(buf);static bool canReadFlag = true;static bool crFlag = false;static bool enterFlag = false;if(canReadFlag && (enterFlag ? bufLen<=bufPos : (int)sizeof(buf)<=bufPos+bufPos)) {if(0<bufLen-bufPos) {memmove(buf, buf+bufPos, bufLen-bufPos);bufLen -= bufPos;}else {bufLen = 0;}char * result = fgets(buf+bufLen, sizeof(buf)-bufLen, stdin);canReadFlag = (result!=NULL);if(result!=NULL) {int n = strlen(result);enterFlag = (n!=(int)sizeof(buf)-1-bufLen || (1<=bufLen+n && buf[bufLen+n-1]=='\n'));bufLen += n;}bufPos = 0;}if(mode==0) {int pos = bufPos;while(true) {char c = buf[pos];if(c==32) {buf[pos++] = '\0';break;}else if(c==10) {if(crFlag) {crFlag = false;if(bufPos==pos) {pos = ++bufPos;continue;}}buf[pos++] = '\0';break;}else if(c==13) {crFlag = true;buf[pos++] = '\0';break;}else if(c==0) {break;}++pos;}const char * ret = buf + bufPos;bufPos = pos;return ret;}else if(mode==1) {int pos = bufPos;while(true) {char c = buf[pos];if(c==10) {if(crFlag) {crFlag = false;if(bufPos==pos) {pos = ++bufPos;continue;}}buf[pos++] = '\0';break;}else if(c==13) {crFlag = true;buf[pos++] = '\0';break;}else if(c==0) {break;}++pos;}const char * ret = buf + bufPos;bufPos = pos;return ret;}else if(mode==2) {return bufLen<=bufPos ? NULL : buf+bufPos;}assert(false);return NULL;}const char * nextCLine() {return nextCLineOrWord(1);}string nextLine() {return nextCLine();}const char * nextCWord() {return nextCLineOrWord(0);}int nextInt() {return atoi(nextCWord());}void echoln() {fputc('\n', stdout);}void echoln(const char * fmt, ...) {va_list arg;va_start(arg, fmt);vprintf(fmt, arg);va_end(arg);fputc('\n', stdout);}set<int> v;int h;int w;int gx;int gy;vector<string> g_map;void func(int x, int y) {if(x==gx && y==gy) {echoln("YES");fflush(stdout);exit(0);}if(v.find((x<<16) | y)!=v.end()) {return;}v.insert((x<<16) | y);if(abs(g_map[y][x]-g_map[y][x+1])<2) {func(x+1, y);}if(abs(g_map[y][x]-g_map[y][x-1])<2) {func(x-1, y);}if(abs(g_map[y][x]-g_map[y-1][x])<2) {func(x, y-1);}if(abs(g_map[y][x]-g_map[y+1][x])<2) {func(x, y+1);}if(g_map[y][x+1]<g_map[y][x] && g_map[y][x+2]==g_map[y][x]) {func(x+2, y);}if(g_map[y][x-1]<g_map[y][x] && g_map[y][x-2]==g_map[y][x]) {func(x-2, y);}if(g_map[y+1][x]<g_map[y][x] && g_map[y+2][x]==g_map[y][x]) {func(x, y+2);}if(g_map[y-1][x]<g_map[y][x] && g_map[y-2][x]==g_map[y][x]) {func(x, y-2);}}int main() {h = nextInt();w = nextInt();int sy = nextInt();int sx = nextInt();gy = nextInt();gx = nextInt();g_map.push_back(string(w+2, 'z'));for(int i=0; i<h; ++i) {g_map.push_back("z"+nextLine()+"z");}g_map.push_back(string(w+2, 'z'));func(sx, sy);echoln("NO");return 0;}