其實這個題是一個簡單的搜索問題，理解了很好做！注意4代表時間復原就行了！具體的在程序里頭，這里就不多說了，深知多說無益，還是要多練的！
1 #include<iostream>
2 using namespace std;
3 int map[12][12],tp[12][12],tt[12][12];
4 int n,m;
5 int Min=0xffffff,sum=0;
6 int x[4]={1,0,0,-1};
7 int y[4]={0,1,-1,0};
8 bool f=true;
9 //數組的交換
10 void fun(int a[12][12],int b[12][12])
11 {
12 for (int i=1;i<=n;i++)
13 for (int j=1;j<=n;j++)
14 a[i][j]=b[i][j];
15
16 }
17 void dfs(int x1,int y1,int sum,int p)
18 {
19 if(map[x1][y1]==3&&p>=0)
20 {
21 // 這里要注意，我是從5開始的，搜到3時，p應該是0以上，
22 //剛開始是沒搞清楚，p大于0,wa了幾次，就是沒找到錯誤！
23 if(Min>sum)Min=sum;
24 //cout<<sum<<endl;
25 f=false;
26 return;
27 }
28 int dx,dy;
29 for (int i=0;i<4;i++)
30 {
31 dx=x1+x[i]; dy=y1+y[i];
32 if (map[dx][dy]!=0&&tp[dx][dy]==0&&p>=1)
33 {
34 if(map[dx][dy]==4)
35 {
36 map[dx][dy]=0;
37 int temp=p;
38 p=5;
39 // cout<<p<<' '<<dx<<' '<<dy<<endl;
40 //輸出路徑，偏于查找當前的坐標位置和剩余時間p
41 fun(tt,tp);
42 memset(tp,0,sizeof(tp));
43 //到4是可以往回搜的，所以前面的走過的路徑應該移除標記
44 //用數組tt記住前面走過的路徑，以便于后面的搜索
45 tp[dx][dy]=1;
46 dfs(dx,dy,sum+1,p);
47 //出來混的，是要還的！這里也一樣！
48 map[dx][dy]=4;
49 tp[dx][dy]=0;
50 p=temp;
51 fun(tp,tt);
52 }
53 else
54 {
55 tp[dx][dy]=1;
56 //cout<<"->"<<p<<' '<<dx<<' '<<dy<<endl;
57 //輸出路徑，偏于查找當前的坐標位置和剩余時間p
58 dfs(dx,dy,sum+1,p-1);
59 tp[dx][dy]=0;
60 }
61 }
62 }
63 }
64 int main()
65 {
66 int t;
67 cin>>t;
68 while (t--)
69 {
70 memset(map,0,sizeof(map));
71 memset(tp,0,sizeof(tp));
72 cin>>n>>m;
73 f=true;
74 int x1,y1,x2,y2;
75 for (int i=1;i<=n;i++)
76 for (int j=1;j<=m;j++)
77 {
78 cin>>map[i][j];
79 if(map[i][j]==2)x1=i,y1=j;
80 //if(map[i][j]==3)x2=i,y2=j;
81 }
82 Min=0xffffff,sum=0;
83 int p=5;
84 map[x1][y1]=0;
85 dfs(x1,y1,sum,5);
86 if(!f)cout<<Min<<endl;
87 else cout<<-1<<endl;
88 }
89 return 0;
90 }
91
posted on 2010-11-09 16:59
路修遠 閱讀(1495)
評論(0) 編輯 收藏 引用 所屬分類:
路修遠