按规则移动机器人 , 问是否能拾得宝藏 。
加了一个控制板 , 还增加了一个控制板移动周期 p
将移动周期变换一下 , 移动一次 就相当于光标向左不耗费时间的移动了一格
搜索思路 : 搜索当前格子到上下左右四个格子所花费的最短时间 。
记录光标的信息 , 和当前格子所需最短时间 。
bfs + bfs
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define PI acos(-1.0)
4 #define MAXN 20
5 #define INF 0x3f3f3f3f
6 int p,min_num;
7 int n,m;
8 int G[MAXN][MAXN];
9 int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
10 struct point
11 {
12 int x;
13 int y;
14 }start,pos;
15 struct base
16 {
17 int cnt;
18 int t;
19 }step[MAXN][MAXN];
20 int read_ch(int x, int y)
21 {
22 char ch;
23 while(ch = getchar())
24 {
25 if(ch == '@')
26 {
27 start.x=x;
28 start.y=y;
29 return true;
30 }
31 if(ch == '.') return true;
32 if(ch == '$')
33 {
34 pos.x=x;
35 pos.y=y;
36 return true;
37 }
38 if(ch == '*') return false;
39 }
40 }
41 void show()
42 {
43 for(int i = 1 ; i <= n ; i ++,cout<<endl)
44 for(int j = 1 ; j <= m ; j ++)
45 printf(step[i][j].cnt == INF?"INF ":"%3d ", step[i][j].cnt);
46 cout<<endl;
47 }
48 int bfs(int t,int cnt,int pos)
49 {
50 queue <int> Q;
51 int temp=0;
52 Q.push(cnt);
53 Q.push(temp);
54 while(!Q.empty())
55 {
56 int x=Q.front();
57 Q.pop();
58 temp=Q.front();
59 Q.pop();
60
61 if(((t+temp) % p == 0) && (t + temp)) x = (x + 3) % 4;
62
63 Q.push((x+3)%4);
64 Q.push(temp+1);
65
66 Q.push(x);
67 Q.push(temp+1);
68
69 Q.push((x+1)%4);
70 Q.push(temp+1);
71
72 if(x == pos) return t+temp+1;
73 }
74 return INF;
75 }
76 void _bfs()
77 {
78 memset(step,0x3f,sizeof(step));
79 step[start.x][start.y].cnt=0;
80 step[start.x][start.y].t=0;
81 queue <int> Q;
82 Q.push(start.x);
83 Q.push(start.y);
84 while(!Q.empty())
85 {
86 int x = Q.front();
87 Q.pop();
88 int y = Q.front();
89 Q.pop();
90
91 if(x < 1 || x > n || y < 1 || y > m || !G[x][y]) continue;
92
93 for(int i=0;i<4;i++)
94 {
95 int xx = x + dir[i][0];
96 int yy = y + dir[i][1];
97
98 if(xx < 1 || xx > n || yy < 1 || yy > m || !G[xx][yy]) continue;
99
100 int temp = bfs(step[x][y].t,step[x][y].cnt,i);
101 if(temp < step[xx][yy].t)
102 {
103 step[xx][yy].t = temp;
104 step[xx][yy].cnt = i;
105 Q.push(xx);
106 Q.push(yy);
107 //printf("x:%2d y:%2d cnt:%2d xx:%2d yy:%2d \n",x,y,i,xx,yy);
108 //show();
109 }
110 }
111 }
112 }
113 int main()
114 {
115 int T;
116 scanf("%d",&T);
117 while(T--)
118 {
119 scanf("%d %d %d",&n,&m,&p);
120 memset(G,false,sizeof(G));
121 for(int i=1;i<=n;i++)
122 for(int j=1;j<=m;j++)
123 G[i][j]=read_ch(i,j);
124 _bfs();
125 printf(step[pos.x][pos.y].t != INF?"%d\n":"YouBadbad\n",step[pos.x][pos.y].t);
126 }
127 return 0;
128 }