8.19 京东后端笔试 算法题

T1、T2 100

T3

每次可以前进的方向(x+k, y) (x, y+k) (x+k)(y+k) (k随意)

从左上角到右下角的最短路线

打暴力 50，应该是一个前缀和优化dp吧，忘了怎么写了，家人催着吃饭提前交了

T3 暴力代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n,m;
char g[2010][2010];
int f[2010][2010] = {0};
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> g[i] + 1;
    memset(f, 0x3f, sizeof f);
    f[1][1] = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(i == 1 && j == 1) continue; 
            for(int k = i - 1; k >= 1; k --)
            {
                if(g[k][j] == '*') break;
                f[i][j] = min(f[i][j], f[k][j] + 1);
            }
            for(int k = j - 1; k >= 1; k --)
            {
                if(g[i][k] == '*') break;
                f[i][j] = min(f[i][j], f[i][k] + 1);
            }
            for(int u = i - 1, v = j - 1; u >= 1 && v >= 1; u --, v --)
            {
                if(g[u][v] == '*') break;
                f[i][j] = min(f[i][j], f[u][v] + 1);
            }    
        }
    }
    if(f[n][m] == 0x3f3f3f3f) cout << -1 << endl;
    else cout << f[n][m] << endl;

正确dp