結果

問題 No.424 立体迷路
ユーザー ramia777ramia777
提出日時 2022-05-22 13:01:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,963 bytes
コンパイル時間 770 ms
コンパイル使用メモリ 94,296 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-20 12:29:39
合計ジャッジ時間 1,529 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicodr
// No.424 立体迷路




//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <list>//list
#include <set> //tree
#include <map> //連想配列
#include <unordered_set> //hash
#include <unordered_map> //hash
#include <algorithm>
#include <iomanip>

using namespace std;

#define START (0)
#define RIGHT (1)
#define UP    (2)
#define LEFT  (3)
#define DOWN  (4)

//二次元可変配列
vector <vector <int>> mass;
vector <vector <int>> memo;

int H,W;
int sx, sy, gx, gy;

typedef struct DIR{
	int dx;
	int dy;
}DIR;


DIR dir[8] =
{
   //dx,dy
  	 0, 1, //0
	-1, 0, //1
	 0,-1, //2
	 1, 0, //3
	 0, 2, //4
	-2, 0, //5
	 0,-2, //6
	 2, 0, //7
};

int ans = 0;

char b[100][100];
char _b[100][100];

void printM(int x0, int y0, int nx, int ny, int dir_index)
{


	cout << "x=" << x0 << ",y=" << y0 << ",nx=" << nx << ",ny=" << ny << ",dir_index=" << dir_index <<endl;

	for (int x = 1; x <= H; x++) 
	{
		for (int y = 1; y <= W; y++)
		{
			cout << _b[x][y] ;
		}
		cout << endl;
	}
	cout << endl;
}

void _printM(void)
{
	
	for (int x = 1; x <= H; x++)
	{
		for (int y = 1; y <= W; y++)
		{
			_b[x][y]='0';
		}
	}
}



//今いる座標 x, y
void solve(int x, int y)
{
	int nx, ny;

	

	if (1 == ans)
		return;

	if ((x == sx) && (y == sy))
	{
		ans = 1;
		return;//たどり着いた
	}



	int dir_index = 0;

	do
	{
		if (ans)
			break;

		
		//次に行く座標
		nx = x + dir[dir_index].dx;
		ny = y + dir[dir_index].dy;

		//printM(x, y, nx, ny, dir_index);

		//次に行く座標が迷路枠内であれば(nxがH制約、nyがW制約であることに注意）
		if ((nx >= 1 && nx <= H) && (ny >= 1 && ny <= W) && (_b[nx][ny] != '1'))
		{
			switch (dir_index)
			{
			case 0:
			case 1:
			case 2:
			case 3:
				if ((abs(b[x][y] - b[nx][ny]) == 1) || (b[x][y] == b[nx][ny]))//隣り合っているブロックの絶対値が1か同じなら... 
				{

					//座標を更新
					x = nx;
					y = ny;

					//マップ更新
					_b[x][y] = '1';
					//cout << ">>>NEXT:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl;
					
					//さらにその次に行く
					solve(x, y);

					//ここに戻ってくるのは行けたけどその先で失敗したとき
					//各種座標をもとに戻しておく
					_b[x][y] = '0';
					x -= dir[dir_index].dx;
					y -= dir[dir_index].dy;

					//cout << "<<<BACK:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl;
				}
				break;
			case 4:
			case 5:
			case 6:
			case 7:
				if (b[x][y] == b[nx][ny])//２つ先のブロックの高さが同じなら... 
				{
					//間のブロックの座標を算出
					int cx, cy;

					cx = (x > nx) ? (x - 1) : ((x < nx) ? (x + 1) : x);
					cy = (y > ny) ? (y - 1) : ((y < ny) ? (y + 1) : y);

					//間のブロックが低いなら...
					if (b[x][y] > b[cx][cy])
					{

						//座標を更新
						x = nx;
						y = ny;

						//マップ更新
						_b[x][y] = '1';

						//cout << ">>>NEXT:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl;

						//さらにその次に行く
						solve(x, y);

						//ここに戻ってくるのは行けたけどその先で失敗したとき
						//各種座標をもとに戻しておく
						_b[x][y] = '0';
						x -= dir[dir_index].dx;
						y -= dir[dir_index].dy;

						//cout << "<<<BACK:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl;
					}
				}
				break;
			}

		}

		//枠外だった、または、枠内だけどその先に行けない

		dir_index++; //方向を変えてみる

	} while (dir_index < 8);

	//行ける候補がなくなったら終了
	return;

}



int main()
{
	cin >> H;
	cin >> W;
	
	cin >> sx;
	cin >> sy;

	cin >> gx;
	cin >> gy;



	for (int x = 1; x <= H; x++)
	{
		for (int y = 1; y <= W; y++)
		{
			cin >> b[x][y];
		}
	}

	//_printM();
	_b[gx][gy] = '1';

	solve(gx, gy);

	cout <<  ((ans == 1) ? "YES" : "NO") << endl;

	//getchar();
	return 0;
}
0