結果

問題 No.367 ナイトの転身
コンテスト
ユーザー kongarishisyamo
提出日時 2016-04-29 23:12:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,392 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,006 ms
コンパイル使用メモリ 58,684 KB
実行使用メモリ 55,332 KB
最終ジャッジ日時 2024-10-04 18:49:19
合計ジャッジ時間 4,631 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:77:24: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         if(dp[0][gy][gx]==INF&&dp[1][gy][gx]==INF) cout<<"-1"<<endl;
      |            ~~~~~~~~~~~~^
main.cpp:77:24: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized]
main.cpp:75:14: warning: ‘sx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |         solve(sx,sy,MODE_B);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:75:14: warning: ‘sy’ may be used uninitialized in this function [-Wmaybe-uninitialized]

ソースコード

diff #
raw source code 

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

#define MODE_B 0
#define MODE_M 1
#define INF 10000000

int dp[2][501][501];
string maze[501];
int H,W;

void ini(){
	for(int i=0;i<2;i++){
		for(int j=0;j<501;j++){
			for(int k=0;k<501;k++){
				dp[i][j][k]=INF;
			}
		}
	}
}

void solve(int x,int y,int MODE){
	//cout<<x<<","<<y<<endl;
	int c=dp[MODE][y][x];
	int dc,dx[8],dy[8];
	if(MODE==MODE_M){
		dc=4;
		dx[0]= 1,dx[1]= 1,dx[2]=-1,dx[3]=-1;
		dy[0]= 1,dy[1]=-1,dy[2]= 1,dy[3]=-1;
	}
	else{
		dc=8;
		dx[0]= 2,dx[1]= 1,dx[2]=-1,dx[3]=-2,dx[4]= 2,dx[5]= 1,dx[6]=-1,dx[7]=-2;
		dy[0]= 1,dy[1]= 2,dy[2]= 2,dy[3]= 1,dy[4]=-1,dy[5]=-2,dy[6]=-2,dy[7]=-1;
	}
	for(int i=0;i<dc;i++){
		int sx=x+dx[i];
		int sy=y+dy[i];
		if(sx>=0&&sx<W&&sy>=0&&sy<H){
			if(maze[sy][sx]=='R'){
				if(c+1<dp[1-MODE][sy][sx]){
					dp[1-MODE][sy][sx]=c+1;
					solve(sx,sy,1-MODE);
				}
			}
			else{
				if(c+1<dp[MODE][sy][sx]){
					dp[MODE][sy][sx]=c+1;
					solve(sx,sy,MODE);
				}
			}
		}
	}
}

int main(){

	cin>>H>>W;
	int sy,sx,gy,gx;
	for(int i=0;i<H;i++){
		cin>>maze[i];
	}
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(maze[i][j]=='S') sy=i,sx=j;
			if(maze[i][j]=='G') gy=i,gx=j;
		}
	}

	ini();
	dp[MODE_B][sy][sx]=0;
	solve(sx,sy,MODE_B);

	if(dp[0][gy][gx]==INF&&dp[1][gy][gx]==INF) cout<<"-1"<<endl;
	else cout<<min(dp[0][gy][gx],dp[1][gy][gx])<<endl;
}
0