NYOJ 1129 Salvation(dfs+方向調整テクニック)
2394 ワード
説明
神秘的な滝町は神秘的な場所で、そこには吸血鬼、狼人、巫女、二重体があります.Klaus(吸血鬼の祖先)はElenaの血液を利用して彼の混血の大軍(吸血鬼&狼人)を発展させるために、神秘的な滝町にも来た.スティーブンはエレナを愛していたので、スティーブンは吸血鬼ハンターを呼び覚まし、エレナを救うことにした.
吸血鬼ハンターは迷路に閉じ込められていて、この迷路には方向感覚を失う特性があります.そこでStefanは、左を基準に(つまり左を優先)、次に前を向いて、右を向いて、どちらも歩けないなら後ろを向いている(つまり右を2回回す)方法を思いついた.彼は上下左右4方向のスペースに1つのグリッドを移動することができ、毎回1分かかります.Stefanはあなたが天賦のプログラマーであることを知った後、彼が吸血鬼ハンターを見つけることができるかどうかを判断することにした.
入力
複数組のテストデータを入力し、1行目はn,m(2“.”スペースを表し、「#」は壁を表し、「T」は初期位置を表し、「X」は吸血鬼ハンターの位置を表す.
しゅつりょく
1行出力し、出力「YES」が見つかれば「NO」を出力します.
サンプル入力
サンプル出力
acコード:
神秘的な滝町は神秘的な場所で、そこには吸血鬼、狼人、巫女、二重体があります.Klaus(吸血鬼の祖先)はElenaの血液を利用して彼の混血の大軍(吸血鬼&狼人)を発展させるために、神秘的な滝町にも来た.スティーブンはエレナを愛していたので、スティーブンは吸血鬼ハンターを呼び覚まし、エレナを救うことにした.
吸血鬼ハンターは迷路に閉じ込められていて、この迷路には方向感覚を失う特性があります.そこでStefanは、左を基準に(つまり左を優先)、次に前を向いて、右を向いて、どちらも歩けないなら後ろを向いている(つまり右を2回回す)方法を思いついた.彼は上下左右4方向のスペースに1つのグリッドを移動することができ、毎回1分かかります.Stefanはあなたが天賦のプログラマーであることを知った後、彼が吸血鬼ハンターを見つけることができるかどうかを判断することにした.
入力
複数組のテストデータを入力し、1行目はn,m(2
しゅつりょく
1行出力し、出力「YES」が見つかれば「NO」を出力します.
サンプル入力
4 4
....
.##.
.##.
TX..
N
4 4
....
.##.
.###
T#.X
Nサンプル出力
YES
NOacコード:
#include<stdio.h>
#include<string.h>
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int v[105][105];
char map[105][105];
int bz,n,m,bs;
int fun(char c)//
{
if(c=='N')return 0;
if(c=='W')return 1;
if(c=='E')return 2;
if(c=='S')return 3;
}
int check(int x,int y)//
{
if(x<0||x>=n||y<0||y>=m||map[x][y]=='#')
return 0;
return 1;
}
void dfs(int x,int y,int bs)
{
if(bz==1)
{
return;
}
for(int i=1;i>-3;i--)
{
int ds=(bs+i+8)%4;//
int nx=x+dx[ds];
int ny=y+dy[ds];
if(check(nx,ny))
{
if(map[nx][ny]=='X')
{
bz=1;
return;
}
if(v[nx][ny]==4)// ， 4
return;
v[nx][ny]++;
dfs(nx,ny,ds);
return;//
}
}
}
int main()
{
char str;
int bx,by;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
for(int j=0;j<m;j++)
{
if(map[i][j]=='T')
{
bx=i;by=j;
}
}
}
getchar();
scanf("%c",&str);
bz=0;
memset(v,0,sizeof(v));
v[bx][by]=1;
dfs(bx,by,fun(str));
if(bz)
printf("YES
");
else
printf("NO
");
}
return 0;
}