結果

問題 No.367 ナイトの転身
ユーザー kongarishisyamokongarishisyamo
提出日時 2016-04-29 23:24:19
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 1,636 bytes
コンパイル時間 821 ms
コンパイル使用メモリ 68,320 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 19:01:15
合計ジャッジ時間 1,553 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:92:44: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |         if(dp[0][gy][gx]==INF&&dp[1][gy][gx]==INF) cout<<"-1"<<endl;
      |                                ~~~~~~~~~~~~^
main.cpp:92:44: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized]

ソースコード

diff # 

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

using namespace std;

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

queue<int> qx,qy,qM;
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=qx.front();qx.pop();
	int y=qy.front();qy.pop();
	int MODE=qM.front();qM.pop();
	//cout<<x<<","<<y<<","<<qx.size()<<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;
					qx.push(sx);
					qy.push(sy);
					qM.push(1-MODE);
				}
			}
			else{
				if(c+1<dp[MODE][sy][sx]){
					dp[MODE][sy][sx]=c+1;
					qx.push(sx);
					qy.push(sy);
					qM.push(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;
	qx.push(sx);
	qy.push(sy);
	qM.push(MODE_B);

	while(!qx.empty()){
		solve();
	}

	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