結果

問題 No.367 ナイトの転身
ユーザー kongarishisyamokongarishisyamo
提出日時 2016-04-29 23:24:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 1,636 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 69,724 KB
実行使用メモリ 5,988 KB
最終ジャッジ日時 2023-07-27 19:06:02
合計ジャッジ時間 2,007 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,272 KB
testcase_01 AC 3 ms
5,272 KB
testcase_02 AC 3 ms
5,372 KB
testcase_03 AC 3 ms
5,436 KB
testcase_04 AC 3 ms
5,392 KB
testcase_05 AC 3 ms
5,388 KB
testcase_06 AC 3 ms
5,372 KB
testcase_07 AC 3 ms
5,504 KB
testcase_08 AC 3 ms
5,272 KB
testcase_09 AC 3 ms
5,620 KB
testcase_10 AC 18 ms
5,988 KB
testcase_11 AC 27 ms
5,968 KB
testcase_12 AC 22 ms
5,496 KB
testcase_13 AC 14 ms
5,792 KB
testcase_14 AC 18 ms
5,608 KB
testcase_15 AC 4 ms
5,308 KB
testcase_16 AC 18 ms
5,500 KB
testcase_17 AC 4 ms
5,532 KB
testcase_18 AC 6 ms
5,388 KB
testcase_19 AC 7 ms
5,424 KB
testcase_20 AC 5 ms
5,336 KB
testcase_21 AC 9 ms
5,424 KB
testcase_22 AC 3 ms
5,616 KB
testcase_23 AC 3 ms
5,316 KB
testcase_24 AC 4 ms
5,308 KB
testcase_25 AC 3 ms
5,368 KB
testcase_26 AC 3 ms
5,268 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:71:15: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sy,sx,gy,gx;
               ^~
main.cpp:71:12: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sy,sx,gy,gx;
            ^~

ソースコード

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