結果

問題 No.124 門松列(3)
コンテスト
ユーザー chaemon
提出日時 2015-01-12 00:07:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,510 bytes
コンパイル時間 740 ms
コンパイル使用メモリ 82,748 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 04:08:38
合計ジャッジ時間 1,529 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #includes {{{
#include <algorithm>
#include <numeric>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <cmath>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

const int INF=0x3f3f3f3f;

typedef long long Int;
typedef unsigned long long uInt;
#ifdef __MINGW32__
typedef double rn;
#else
typedef long double rn;
#endif

typedef pair<int,int> pii;

/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}

struct S{
	int x,y,d;
	S(int x,int y,int d):x(x),y(y),d(d){}
};

int W,H;

int M[110][110];

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int dist[110][110][4], vis[110][110][4];

queue<S> q;

bool inner(int x,int y){
	return 0<=x and x<W and 0<=y and y<H;
}

bool is_kamdomatsu(int x0,int y0,int x1,int y1,int x2,int y2){
	return (M[x0][y0]-M[x1][y1])*(M[x0][y0]-M[x2][y2])<0
	 or (M[x2][y2]-M[x0][y0])*(M[x2][y2]-M[x1][y1])<0;
}

int bfs(){
	memset(vis,false,sizeof(vis));
	memset(dist,63,sizeof(dist));
	q.push(S(0,0,0));
	q.push(S(0,0,1));
	dist[0][0][0]=1;
	dist[0][0][1]=1;
	while(!q.empty()){
		S s = q.front();
		int x0=s.x, y0=s.y, d0=s.d;
		q.pop();
		if(vis[x0][y0][d0])continue;
//		cout<<x0<<" "<<y0<<" "<<d0<<" "<<dist[x0][y0][d0]<<endl;
		vis[x0][y0][d0]=true;
		int x1=x0+dir[d0][0], y1=y0+dir[d0][1];
		/*
		if(x1==W-1 and y1==H-1){
			return dist[x0][y0][d];
		}
		*/
		assert(inner(x1,y1));
		REP(d1,4){
			int x2 = x1+dir[d1][0], y2 = y1+dir[d1][1];
			if(not inner(x2,y2) or not is_kamdomatsu(x0,y0,x1,y1,x2,y2))continue;
			if(dist[x0][y0][d0]+1<dist[x1][y1][d1]){
				dist[x1][y1][d1]=dist[x0][y0][d0]+1;
				q.push(S(x1,y1,d1));
			}
		}
	}
	return min(dist[W-2][H-1][0],dist[W-1][H-2][1]);
}

int main(){
	cin>>W>>H;
	REP(i,W)REP(j,H)cin>>M[i][j];
	int ans=bfs();
	if(ans==INF)ans=-1;
	cout<<ans<<endl;
	return 0;
}
0