HDU 1728迷宮から脱出(DFS)
2627 ワード
迷宮から逃げる
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 34264 Accepted Submission(s): 8372
Problem Description
mを1つ与える× n(m行、n列)の迷路、迷路の中には2つの位置があり、gloriaは迷路の1つの位置から別の位置に行きたいと思っています.もちろん迷路の中には空き地があり、gloriaは通り抜けることができます.障害がある場所もあります.彼女は迂回しなければなりません.迷路の1つの位置から、それに隣接する4つの位置までしか歩けません.もちろん、歩いているうちにgloriaは迷路の外に行けません.頭が痛いのは、gloriaは方向感覚のない人なので、彼女は歩いている間に、あまり曲がってはいけません.そうしないと、彼女は気絶します.与えられた2つの位置は空き地であると仮定し,初期にgloriaが向いている方向は未定であり,彼女は4つの方向のいずれかを選択して出発することができ,1回のカーブではない.gloriaは一つの位置から別の位置に行けますか?
Input
第1の挙動は1つの整数t(1≦t≦100)であり、試験データの個数を表し、次にt群の試験データであり、各群の試験データのうち、第1の挙動は2つの整数m,n(1≦m,n≦100)であり、それぞれ迷宮の行数と列数を表し、次にm行であり、各行はn文字を含み、文字'.'はこの位置が空き地であり、文字'*'はこの位置が障害であることを示し、入力データにはこの2つの文字しかなく、各テストデータの最後の動作は5つの整数k,x 1,y 1,x 2,y 2(1≦k≦10,1≦x 1,x 2≦n,1≦y 1,y 2≦m)であり、ここでkはgloriaが最も回転可能な曲数を表し、(x 1,y 1)、(x 2,y 2)は2つの位置を表し、x 1,x 2は列、y 1,y 2は行に対応する.
Output
各テストデータのセットは1行に対応し、gloriaが1つの位置から別の位置に移動できれば「yes」を出力し、そうでなければ「no」を出力する.
Sample Input
Sample Output
问题解:DFSで大体の考え方を书くと、4つの方向を歩いて、各地方の最小転向回数を记录して、もしゴールに着いた时、転向がテーマの要求に等しいものより小さいならば、okになります.しかし、最小転向回数を記録するのは難題で、私も自分で方法を試してみましたが、タイムアウトして、枝を切るのが足りないのではないでしょうか.やはり多くの問題解を調べてみると、一つの配列で最小ステアリング回数を保存し、枝を切る方法があることがわかりました.この問題は枝を切ることが大切だ.さもないとタイムアウトになるに違いない.
ps:この問題はx 1を言って、y 1は列と行を表しています!
具体的なコードは以下の通りです.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 34264 Accepted Submission(s): 8372
Problem Description
mを1つ与える× n(m行、n列)の迷路、迷路の中には2つの位置があり、gloriaは迷路の1つの位置から別の位置に行きたいと思っています.もちろん迷路の中には空き地があり、gloriaは通り抜けることができます.障害がある場所もあります.彼女は迂回しなければなりません.迷路の1つの位置から、それに隣接する4つの位置までしか歩けません.もちろん、歩いているうちにgloriaは迷路の外に行けません.頭が痛いのは、gloriaは方向感覚のない人なので、彼女は歩いている間に、あまり曲がってはいけません.そうしないと、彼女は気絶します.与えられた2つの位置は空き地であると仮定し,初期にgloriaが向いている方向は未定であり,彼女は4つの方向のいずれかを選択して出発することができ,1回のカーブではない.gloriaは一つの位置から別の位置に行けますか?
Input
第1の挙動は1つの整数t(1≦t≦100)であり、試験データの個数を表し、次にt群の試験データであり、各群の試験データのうち、第1の挙動は2つの整数m,n(1≦m,n≦100)であり、それぞれ迷宮の行数と列数を表し、次にm行であり、各行はn文字を含み、文字'.'はこの位置が空き地であり、文字'*'はこの位置が障害であることを示し、入力データにはこの2つの文字しかなく、各テストデータの最後の動作は5つの整数k,x 1,y 1,x 2,y 2(1≦k≦10,1≦x 1,x 2≦n,1≦y 1,y 2≦m)であり、ここでkはgloriaが最も回転可能な曲数を表し、(x 1,y 1)、(x 2,y 2)は2つの位置を表し、x 1,x 2は列、y 1,y 2は行に対応する.
Output
各テストデータのセットは1行に対応し、gloriaが1つの位置から別の位置に移動できれば「yes」を出力し、そうでなければ「no」を出力する.
Sample Input
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3Sample Output
no
yes问题解:DFSで大体の考え方を书くと、4つの方向を歩いて、各地方の最小転向回数を记录して、もしゴールに着いた时、転向がテーマの要求に等しいものより小さいならば、okになります.しかし、最小転向回数を記録するのは難題で、私も自分で方法を試してみましたが、タイムアウトして、枝を切るのが足りないのではないでしょうか.やはり多くの問題解を調べてみると、一つの配列で最小ステアリング回数を保存し、枝を切る方法があることがわかりました.この問題は枝を切ることが大切だ.さもないとタイムアウトになるに違いない.
ps:この問題はx 1を言って、y 1は列と行を表しています!
具体的なコードは以下の通りです.
#include
#include
#include
using namespace std;
int map[102][102];
int turn[102][102];//
int d[4][2]={0,1,1,0,0,-1,-1,0};
int a,b,K,x1,y1,x2,y2,ok;
void DFS(int i,int j,int dir)
{
if(i==x2&&j==y2&&turn[i][j]<=K)
{
ok=1;
return ;
}
if(turn[i][j]>K)//( )
return ;
if(i!=x2&&j!=y2&&turn[i][j]==K)//( )
return;
for(int k=0;k<4;k++)
{
int x=i+d[k][0];
int y=j+d[k][1];
if(x<=0||x>a||y<=0||y>b||map[x][y]==0)// ( )
continue;
if(turn[x][y]>T;
while(T--)
{
cin>>a>>b;
memset(map,0,sizeof(map));
memset(turn,1000000,sizeof(turn));
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
{
char m;
cin>>m;
if(m=='.')
map[i][j]=1;
else
map[i][j]=0;
}
cin>>K>>y1>>x1>>y2>>x2;
ok=0;
turn[x1][y1]=0;
DFS(x1,y1,-1);
if(ok)
cout<