题目链接:吃豆人
比赛的时候写的bfs,纠结要不要有vis数组设置已被访问,没有的话死循环,有的话就不一定是最优解了。【此时先到的不一定就是时间最短的。】于是换dfs,WA。
赛后写了个炒鸡聪明的dfs,TLE,才发现时间复杂度好像是4^(n*m)。T_T
依然感觉这个dfs很棒。
bfs已AC,怎么解决的这个问题呢,如果当前位置next 被优化了则加入队列,以此优化其他位置,否则不加入队列。T_T好有道理~~~
感觉bfs和dfs好神奇的说~
dfs TLE代码:
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <cmath>
#include <queue>
#define inf 100000000
using namespace std; char mp[30][30]; struct Node{
int x, y;
}st, ed, tool, temp, nxt; int vis[30][30];
double step[30][30];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int n, m; bool check(Node temp) {
if (temp.x >= 0 && temp.x < n && temp.y >= 0 && temp.y < m && !vis[temp.x][temp.y] && mp[temp.x][temp.y] != 'X') {
return true;
)}
return false;
} void get(Node temp, Node ed) {
if (temp.x == ed.x) {
int minn = min(temp.y, ed.y);
int maxm = max(temp.y, ed.y);
for (int i=minn+1; i<maxm; ++i) {
if (mp[ed.x][i] == 'X' || mp[ed.x][i] == 'S') return;
}
int t = abs(temp.y - ed.y);
step[ed.x][ed.y] = min(step[temp.x][temp.y]+t*0.2,step[ed.x][ed.y]);
}
else if (temp.y == ed.y) {
int minn = min(temp.x, ed.x);
int maxm = max(temp.x, ed.x);
for (int i=minn+1; i<maxm; ++i) {
if (mp[i][ed.y] == 'X' || mp[i][ed.x] == 'S') return;
}
int t = abs(temp.x - ed.x);
step[ed.x][ed.y] = min(step[temp.x][temp.y]+t*0.2, step[ed.x][ed.y]);
}
} void dfs(Node st, Node ed, bool v) {
for (int i=0; i<4; ++i) {
nxt.x = st.x + dir[i][0];
nxt.y = st.y + dir[i][1];
if (check(nxt)) {
double t = step[st.x][st.y];
if (v) t += 0.5;
else t += 1;
step[nxt.x][nxt.y] = min(step[nxt.x][nxt.y], t);
vis[nxt.x][nxt.y] = 1;
get(nxt, ed);
if (nxt.x == tool.x && nxt.y == tool.y) dfs(nxt, ed, true);
else dfs(nxt, ed, v);
}
}
vis[st.x][st.y] = 0;
return;
} int main() {
while(~scanf("%d%d", &n, &m)) {
bool v = false;
memset(vis, 0, sizeof(vis));
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
step[i][j] = inf;
}
}
getchar();
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
scanf("%c", &mp[i][j]);
if (mp[i][j] == 'P') {
st.x = i, st.y = j;
}
else if (mp[i][j] == 'B') {
ed.x = i, ed.y = j;
}
else if (mp[i][j] == 'S') {
tool.x = i, tool.y = j;
}
}
if (i != n-1) scanf("\n");
}
step[st.x][st.y] = 0;
vis[st.x][st.y] = 1;
dfs(st, ed, v);
get(st, ed);
double ans = step[ed.x][ed.y];
if (ans != inf)
printf("%.1lf\n", ans);
else printf("-1\n");
}
return 0;
}
bfs AC 代码:
/*
直接一个bfs,用两个数组保存有工具和没有工具时需要的时间。
*/ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#define inf 1000000000
using namespace std; char mp[30][30];
int n, m; struct Node {
int x, y, s; // 0 表示没有工具 1 表示有工具了。
}st, ed, temp, now, nxt; int step[30][30][2]; int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; void bfs(Node st) {
queue<Node> que;
que.push(st);
step[st.x][st.y][0] = 0;
while(!que.empty()) {
now = que.front();
que.pop();
if (now.x == ed.x) {
int miny = min(now.y, ed.y);
int maxy = max(now.y, ed.y);
bool get = true;
for (int y=miny+1; y<maxy; ++y) {
if (mp[now.x][y] == 'X' || mp[now.x][y] == 'S') {
get = false;
break;
}
}
if (get) step[ed.x][ed.y][now.s] = min(step[now.x][now.y][now.s] + 2 * (maxy - miny), step[ed.x][ed.y][now.s]);
} if (now.y == ed.y) {
int minx = min(now.x, ed.x);
int maxx = max(now.x, ed.x);
bool get = true;
for (int x=minx+1; x<maxx; ++x) {
if (mp[x][ed.y] == 'X' || mp[x][ed.y] == 'S') {
get = false;
}
}
if (get) step[ed.x][ed.y][now.s] = min(step[now.x][now.y][now.s] + 2 * (maxx - minx), step[ed.x][ed.y][now.s]);
} int T;
for (int i=0; i<4; ++i) {
nxt.x = now.x + dir[i][0];
nxt.y = now.y + dir[i][1];
nxt.s = now.s;
if (nxt.x<0 || nxt.y<0 || nxt.x>=n || nxt.y>=m) continue;
if (mp[nxt.x][nxt.y] == 'X') continue;
if (now.s) T = 5;
else T = 10;
if (step[nxt.x][nxt.y][nxt.s] > step[now.x][now.y][now.s] + T) {
step[nxt.x][nxt.y][nxt.s] = step[now.x][now.y][now.s] + T;
if (mp[nxt.x][nxt.y] == 'S') {
nxt.s = 1;
step[nxt.x][nxt.y][1] = step[nxt.x][nxt.y][0];
}
que.push(nxt);
}
}
}
} int main() {
while(cin >> n >> m) {
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
for (int k=0; k<2; ++k) {
step[i][j][k] = inf;
}
}
} for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
cin >> mp[i][j];
if (mp[i][j] == 'P') {
st.x = i, st.y = j;
}
else if (mp[i][j] == 'B') {
ed.x = i, ed.y = j;
}
}
} st.s = 0;
bfs(st);
int ans = min(step[ed.x][ed.y][0], step[ed.x][ed.y][1]);
if (ans == inf) cout << "-1\n";
else printf("%.1lf\n", ans*1.0/10);
}
return 0;
}