Buggy Robot（Dijkstra + DP）

原题链接

参考

题意

思路

dp思路 + dijkstra

dp:

$d[i][j][k]$ 表示用前k步时走到 $(i，j)$ ,最小的修改次数，

下面公式给的都只是一个大概意思，可以这样理解，实际上用优先队列版的Dijkstra时需要写成if判断的形式，判断最小值是否更新再放进队列。

添一步走： $$d[x+xx[i]][y+yy[i]][k]=min(d[x][y][k]+1,d[x+xx[i]][y+xx[i]][k])$$

添一步走的思想就是我在当前这一步的基础上加一步，使它不走到操作序列中的下一个，使它的方案还在这一步中，但是位置变了操作次数也变了。

删一步走$$d[x][y][k+1]=min(d[x][y][k+1],d[x][y][k]+1)$$

此处要注意K的大小，要控制在给的操作串长度以内，否则没意义还会死循环！

删一步走的意思是，在走下一步时不走下一步，所以还留在原位，但是实际上已经到下一步了，只是没有走而已，然后操作次数要+1；

直接走

此处要注意K的大小，要控制在给的操作串长度以内，否则没意义还会死循环！

如果走得了$$d[x+xx[i]][y+yy[i]][k+1]=min(d[x+xx[i]][y+yy[i]][k+1],d[x][y][k])$$

是直接走好还是到达那一步已经有了更好的走法

如果走不了（出界或撞墙）$$f[x][y][k+1]=min(f[x][y][k+1],f[x][y][k])$$

下一步走不了所以还是留在原位，那么下一步到当前位置的操作步数可以用当前这一步来更新，因为反正动不了，也没有走，也不需要增加操作步数，看看是否要更新

Dijkstra

每次选操作次数最小的点，即距离最近的点作为队头，用它来更新所有连边，更新方式见上，然后把被更新了最短距离的点再放进队列，直到把所有距离都走完为止。

代码

#include<bits/stdc++.h> 
using namespace std;
const int N = 150;int xx[4] = {
    1, 0, -1, 0};
int yy[4] = {
    0, 1, 0, -1};struct node{
    int x; int y;int k;//当前已经走过序列中的第几步，每次更新的都是它的后一步 int step;//第几次操作 bool operator < (const node &b) const {
    return step > b.step;}
};int n, m;
char g[N][N];
int d[N][N][N];
char s[N];
int len;
int sx, sy, ex, ey; //起点终点 void bfs()
{
    priority_queue<node> q;q.push({
    sx, sy, 0, 0}); //放入起点 memset(d, 0x3f3f3f3f, sizeof d); //初始化距离d[sx][sy][0] = 0;while (!q.empty()){
    node t = q.top();q.pop();int x = t.x, y = t.y, k = t.k, step = t.step;if (g[x][y] == 'E') continue;// cout << x << " " << y << " " << k << " " << step << endl;//添一步走for (int i = 0; i < 4; i ++ ) {
    int dx = x + xx[i];int dy = y + yy[i];//此处也要判断可以走，因为走不了没有意义 if (d[dx][dy][k] > step + 1 && dx >= 1 && dx <= n && dy >= 1 && dy <= m && g[dx][dy] != '#'){
    d[dx][dy][k] = step + 1; //更新距离q.push({
    dx, dy, k, step + 1}); //放入队列 }}if (k + 1 <= len) //防止死循环 {
    //删一步走 if (d[x][y][k + 1] > d[x][y][k] + 1) {
    d[x][y][k + 1] = step + 1;q.push({
    x, y, k + 1, step + 1});}int dx = x, dy = y; //直接走if (s[k + 1] == 'U') {
    dx --;}else if (s[k + 1] == 'D'){
    dx ++;}else if (s[k + 1] == 'L'){
    dy --;}else if (s[k + 1] == 'R'){
    dy ++;}//如果可以走 if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && g[dx][dy] != '#'){
    if (d[dx][dy][k + 1] > step){
    d[dx][dy][k + 1] = step;q.push({
    dx, dy, k + 1, step});}}else //撞墙or出界 {
    if (d[x][y][k + 1] > step) {
    d[x][y][k + 1] = step;q.push({
    x, y, k + 1, step});}}}}
}int main()
{
    cin >> n >> m;for (int i = 1; i <= n; i ++ ){
    for (int j = 1; j <= m; j ++ ){
    cin >> g[i][j];if (g[i][j] == 'R'){
    sx = i;sy = j;}if (g[i][j] == 'E'){
    ex = i;ey = j;}}}scanf("%s", s + 1);len = strlen(s + 1);bfs();int ans = 0x3f3f3f3f;for (int i = 0; i <= len; i ++ ){
    ans = min(ans, d[ex][ey][i]);}cout << ans << endl;return 0;
}

总结

好！好！好！

珍贵手记

学习方法记录！