hdu 1728:迷宮から逃げる(DFS、枝切り)
15321 ワード
迷宮から逃げる
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13562 Accepted Submission(s): 3221
Problem Description
mを1つ与える× n(m行、n列)の迷路、迷路の中には2つの位置があり、gloriaは迷路の1つの位置から別の位置に行きたいと思っています.もちろん迷路の中には空き地があり、gloriaは通り抜けることができます.障害がある場所もあります.彼女は迂回しなければなりません.迷路の1つの位置から、それに隣接する4つの位置までしか歩けません.もちろん、歩いているうちにgloriaは迷路の外に行けません.頭が痛いのは、gloriaは方向感覚のない人なので、彼女は歩いている間に、あまり曲がってはいけません.そうしないと、彼女は気絶します.与えられた2つの位置は空き地であると仮定し,初期にgloriaが向いている方向は未定であり,彼女は4つの方向のいずれかを選択して出発することができ,1回のカーブではない.gloriaは一つの位置から別の位置に行けますか?
Input
第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)は、xの2つの位置を表す
1,x
2対応列、y
1, y
2対応する行.
Output
各テストデータのセットは1行に対応し、gloriaが1つの位置から別の位置に移動できれば「yes」を出力し、そうでなければ「no」を出力する.
Sample Input
Sample Output
no
yes
Source
「ネット新恩普杯」杭州電子科学技術大学プログラム設計招待試合
Recommend
lcy | We have carefully selected several similar problems for you:
1072
1372
1254
2102
1548
検索、DFS枝切り.
この問題はBFSでやると簡単ですが、DFSだとタイムアウトしやすいので、枝切りに注意が必要です.
一つの配列でカーブの回数を記録し、次にカーブする場合は、次のステップよりも元の記憶されているカーブの回数が大きいかどうかを判断し、元のものよりも大きい場合は、このステップを歩かないという考え方です.これは主な枝切りであり,多くの繰返し過程を回避した.
コード:
Freecode : www.cnblogs.com/yym2013
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13562 Accepted Submission(s): 3221
Problem Description
mを1つ与える× n(m行、n列)の迷路、迷路の中には2つの位置があり、gloriaは迷路の1つの位置から別の位置に行きたいと思っています.もちろん迷路の中には空き地があり、gloriaは通り抜けることができます.障害がある場所もあります.彼女は迂回しなければなりません.迷路の1つの位置から、それに隣接する4つの位置までしか歩けません.もちろん、歩いているうちにgloriaは迷路の外に行けません.頭が痛いのは、gloriaは方向感覚のない人なので、彼女は歩いている間に、あまり曲がってはいけません.そうしないと、彼女は気絶します.与えられた2つの位置は空き地であると仮定し,初期にgloriaが向いている方向は未定であり,彼女は4つの方向のいずれかを選択して出発することができ,1回のカーブではない.gloriaは一つの位置から別の位置に行けますか?
Input
第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)は、xの2つの位置を表す
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
Source
「ネット新恩普杯」杭州電子科学技術大学プログラム設計招待試合
Recommend
lcy | We have carefully selected several similar problems for you:
1072
1372
1254
2102
1548
検索、DFS枝切り.
この問題はBFSでやると簡単ですが、DFSだとタイムアウトしやすいので、枝切りに注意が必要です.
一つの配列でカーブの回数を記録し、次にカーブする場合は、次のステップよりも元の記憶されているカーブの回数が大きいかどうかを判断し、元のものよりも大きい場合は、このステップを歩かないという考え方です.これは主な枝切りであり,多くの繰返し過程を回避した.
コード:
1 #include <stdio.h>
2 #include <string.h>
3 #define inf 0x7fffffff
4 int m,n,k,x1,y1,x2,y2; 5 char a[110][110]; 6 int w[110][110]; 7 bool isv[110][110]; 8 int dx[4] = {0,1,0,-1}; 9 int dy[4] = {1,0,-1,0}; 10 bool f; 11 bool judge(int x,int y) 12 { 13 if(x>m || x<1 || y>n || y<1) 14 return true; 15 if(isv[x][y]) 16 return true; 17 if(a[x][y] == '*') 18 return true; 19 return false; 20 } 21 void dfs(int cx,int cy,int d) 22 { 23 if(cx==x2 && cy==y2){ 24 if(w[x2][y2]<=k) 25 f = true; 26 return ; 27 } 28 int i; 29 for(i=0;i<4;i++){ 30 int nx = cx + dx[i]; 31 int ny = cy + dy[i]; 32 if(d!=i && w[cx][cy]==k) // （ ） k，
33 continue; 34 if(d != -1 && i != d && w[nx][ny] < w[cx][cy] + 1) // 。 ， ，
35 continue; 36 if(judge(nx,ny)) //
37 continue; 38 w[nx][ny] = w[cx][cy]; 39 if(d!=i) 40 w[nx][ny]++; 41 if(w[nx][ny]>k) 42 continue; 43 //
44 isv[nx][ny] = true; 45 dfs(nx,ny,i); 46 isv[nx][ny] = false; 47 if(f) return ; 48 } 49 } 50 int main() 51 { 52 int i,j,T; 53 scanf("%d",&T); 54 while(T--){ 55 f = false; 56 scanf("%d%d%*",&m,&n); 57 for(i=1;i<=m;i++){ //
58 for(j=1;j<=n;j++){ 59 scanf("%c",&a[i][j]); 60 w[i][j] = inf; 61 } 62 scanf("%*"); 63 } 64 scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2); 65 memset(isv,0,sizeof(isv)); 66 isv[x1][y1] = true; 67 w[x1][y1] = -1; 68 dfs(x1,y1,-1); 69 if(f) 70 printf("yes
"); 71 else
72 printf("no
"); 73 } 74 return 0; 75 }Freecode : www.cnblogs.com/yym2013