結果

問題 No.367 ナイトの転身
ユーザー kotatsugame
提出日時 2020-02-11 23:53:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 949 bytes
コンパイル時間 834 ms
コンパイル使用メモリ 76,800 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-10-01 12:29:39
合計ジャッジ時間 2,111 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#include<queue>
using namespace std;
int H,W;
string s[500];
int d[500][500][2];
int dx[2][8]={
	{1,2,2,1,-1,-2,-2,-1},
	{1,1,-1,-1}
};
int dy[2][8]={
	{2,1,-1,-2,-2,-1,1,2},
	{1,-1,-1,1}
};
main()
{
	cin>>H>>W;
	queue<pair<pair<int,int>,bool> >Q;
	for(int i=0;i<H;i++)
	{
		cin>>s[i];
		for(int j=0;j<W;j++)
		{
			d[i][j][0]=d[i][j][1]=1e9;
			if(s[i][j]=='S')
			{
				Q.push(make_pair(make_pair(i,j),false));
				d[i][j][0]=0;
			}
		}
	}
	while(!Q.empty())
	{
		int x=Q.front().first.first,y=Q.front().first.second;
		bool w=Q.front().second;
		Q.pop();
		int now=d[x][y][w];
		if(s[x][y]=='G')
		{
			cout<<now<<endl;
			return 0;
		}
		for(int r=0;r<(w?4:8);r++)
		{
			int tx=x+dx[w][r];
			int ty=y+dy[w][r];
			if(0<=tx&&tx<H&&0<=ty&&ty<W)
			{
				bool nw=s[tx][ty]=='R'?!w:w;
				if(d[tx][ty][nw]>now+1)
				{
					d[tx][ty][nw]=now+1;
					Q.push(make_pair(make_pair(tx,ty),nw));
				}
			}
		}
	}
	cout<<-1<<endl;
}
0