其实这个题是一个简单的搜索问题，理解了很好做！注意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
路修远 阅读(1489)
评论(0) 编辑 收藏 引用 所属分类:
路修远