不知道为什么比赛的时候一直想着用DFS 来写
一直想剪枝结果还是TLE = =
这题数据量不大，又是问最优解，那么一般来说是用 BFS 来写
int commandi[4] = {1, 2, 3, 4};
我定义了一个方向数组，其实题目意思中的，指针移动还有操作版的变化本质上都是指针的移动
在此只需要 额外定义一个变量 cur 在数组 commandi 中循环移动即可
这道题目还是因为数据量不大吧，直接用 STL 中的 Queue 即可，优先队列肯定会更快。
总体来说，还是一道容易题。
Source Code :
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ;
const int MAXN = ;
const int INF = 0x3f3f3f3f ; const int dir_x[] = {, , , -, };
const int dir_y[] = {, -, , , }; struct sc {
int x, y;
int time;
int cur;
} st, ed; int n, m, p;
char a[][];
bool vis[][][];
int commandi[] = {, , , };
queue <sc> q; bool check (int x, int y) {
return x >= && x <= n && y >= && y <= m;
} int left (int &cur) {
cur = (cur - + ) % ;
} int right (int & cur) {
cur = (cur + + ) % ;
} void solve (struct sc v) {
++v.time;
if (v.time % p == ) {
left (v.cur);
}
if (vis[v.x][v.y][commandi [v.cur]] == false) {
vis[v.x][v.y][commandi [v.cur]] = true;
q.push (v);
}
} void bfs () {
int ans = -INF; sc e;
e = st;
e.time = ;
e.cur = ; memset (vis, , sizeof (vis));
vis [e.x][e.y][commandi [e.cur]] = true;
q.push (e); while (!q.empty ()) {
sc u = q.front ();
q.pop ();
if ((u.x == ed.x && u.y == ed.y) || '$' == a[u.x][u.y]) {
ans = u.time;
break;
} sc v = u; //to left
left (v.cur);
solve (v); v = u; //to right
right (v.cur);
solve (v); v = u; //wait
solve (v); v = u; //press
int dr = commandi [v.cur];
v.x += dir_x[dr];
v.y += dir_y[dr];
if (!check (v.x, v.y)) continue;
if ('*' == a[v.x][v.y]) continue;
solve (v);
} if (-INF == ans) {
cout << "YouBadbad" << endl;
} else {
cout << ans << endl;
}
} int main () {
int i, j, t; cin >> t;
while (t--) {
while (!q.empty ()) q.pop ();
cin >> n >> m >> p;
for (i = ; i <= n; ++i) {
for (j = ; j <= m; ++j) {
cin >> a[i][j];
if ('@' == a[i][j]) {
st.x = i;
st.y = j;
} else if ('$' == a[i][j]) {
ed.x = i;
ed.y = j;
}
}
}
bfs ();
} return ;
} /*
10 10 3
@.........
..........
..........
..........
..........
..........
..........
..........
..........
.........$ 10 5 3
@....
.....
.....
.....
.....
.....
.....
.....
.....
....$
*/