讨论/《美团 2021 届秋季校园招聘笔试真题》 - 十字路口/
《美团 2021 届秋季校园招聘笔试真题》 - 十字路口
共 3 个回复

拉跨,将就着看吧。。。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, xs, ys, xt, yt;
    cin>>n>>m>>xs>>ys>>xt>>yt;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cin>>a[i][j];
        }
    }
    vector<vector<int>> b(n + 1, vector<int>(m + 1));
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            cin>>b[i][j];
        }
    }
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, -1));
    dist[xs][ys] = 0;
    queue<pair<int, int>> qu;
    qu.push({xs, ys});
    while(!qu.empty()){
        auto [x, y] = qu.front();
        qu.pop();
        if(x == xt && y == yt){
            cout<<dist[x][y]<<endl;
            return 0;
        }
        int index = a[x][y] + b[x][y];
        int res = dist[x][y] % index;
        if(res < a[x][y]){
            if(x - 1 >= 1 && dist[x - 1][y] == -1){
                dist[x - 1][y] = dist[x][y] + 1;
                qu.push({x - 1, y});
            }
            if(x + 1 <= n && dist[x + 1][y] == -1){
                dist[x + 1][y] = dist[x][y] + 1;
                qu.push({x + 1, y});
            }
            if(dist[x][y] != -1){
                dist[x][y] ++;
                qu.push({x, y});
            }
        }
        if(res >= a[x][y] && res < index){
            if(y - 1 >= 1 && dist[x][y - 1] == -1){
                dist[x][y - 1] = dist[x][y] + 1;
                qu.push({x, y - 1});
            }
            if(y + 1 <= m && dist[x][y + 1] == -1){
                dist[x][y + 1] = dist[x][y] + 1;
                qu.push({x, y + 1});
            }
            if(dist[x][y] != -1){
                dist[x][y] ++;
                qu.push({x, y});
            }
        }
    }
    return 0;
}

smjb水数据
dij不加vis都能过
时间内存都超100%
服了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int N = 105;
struct Node {
    int x, y;
    Node() {}
    Node(int _x, int _y) {x=_x;y=_y;}
    bool operator < (const Node other) const {
        return x == other.x ? (y < other.y) : (x < other.x);
    }
    int id(int n) {
        return (x - 1) * n + y;
    }
}pos[N * N];
int a[N][N], b[N][N];
Node st, ed;
int dis[N * N], vis[N * N], n, m, dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
bool check(int x, int y) {
    return x > 0 && y > 0 && x <= n && y <= m;
}
void solve() {
    cin >> n >> m;
    cin >> st.x >> st.y;
    cin >> ed.x >> ed.y;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            dis[Node(i, j).id(n)] = 1e18;
            cin >> a[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin >> b[i][j];
        }
    }
    priority_queue<pair<int, Node> ,vector<pair<int, Node>>, greater<pair<int, Node>>>s;
    dis[st.id(n)] = 0;
    s.push({0, st});
    while(!s.empty()) {
        int disu = (s.top()).first;
        auto u = (s.top()).second;
        s.pop();
        if(vis[u.id(n)]) continue;
        vis[u.id(n)] = 1;
        if(disu != dis[u.id(n)]) continue;
        for(int i=0;i<4;i++) {
            int nowx = u.x + dx[i], nowy = u.y + dy[i];
            int con = a[u.x][u.y] + b[u.x][u.y];
            Node v(nowx, nowy);
            if(!check(nowx, nowy)) continue;
            int delta;
            if(dy[i] == 0) { // updown
                int iner_pos = disu % con;
                if(iner_pos < a[u.x][u.y]) {
                    delta = 1;
                } else {
                    delta = con - iner_pos + 1;
                }

            } else {
                int iner_pos = disu % con;
                if(iner_pos >= a[u.x][u.y]) {
                    delta = 1;
                } else {
                    delta = a[u.x][u.y] - iner_pos + 1;
                }
            }
            if(dis[v.id(n)] > disu + delta) {
                dis[v.id(n)] = disu + delta;
                if(!vis[v.id(n)])
                s.push({dis[v.id(n)], v});
            }
        }
    }
    cout << dis[ed.id(n)];
}
signed main() {
    //fastio;
    int t = 1;
    while(t--) solve();
    return 0;
}

dij模板题