結果

問題 No.424 立体迷路
ユーザー coluncolun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0