#118736 (C++11) No.424 立体迷路

• 問題: No.424 立体迷路
• ユーザー: colun
• 提出日時: 2016-09-22 23:01:18
• 言語: C++11 (gcc 11.4.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	2 ms; 5,376 KB

ソースコード

#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;
}