首页 > 试题广场 >

十字路口

[编程题]十字路口

热度指数：1583 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在小美和小团生活的城市中，有n行m列共计n*m个十字路口，第i行j列的十字路口有两个属性a_ij，b_ij。当行人处在i行j列的路口，对于任意非负整数k:

当时间处在[k*a_ij+k*b_ij), (k+1)*a_ij+k*b_ij)时，行人可以选择走到i±1行j列的路口。

当时间处在[(k+1)*a_ij+k*b_ij), (k+1)*a_ij+(k+1)*b_ij)时，行人可以选择走到i行j±1列的路口。

每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于n*m个路口当中。可以选择原地静止不动。

在第0时刻，小美处在x_s行y_s列的十字路口处，要去x_t行y_t列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?

输入描述:

第一行六个正整数n，m，x_s，y_s，x_t，y_t，含义如上文所示。以样例第一行【5、5、2、4、4、3】共计6个数字为例，前两位数字代表有5*5的二维数组，三、四位数字代表小美处在2行4列的十字路口处，五、六位数字代表要去4行3列的十字路口找小团。

接下来n行每行m个正整数，在样例中为第一个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性a_ij。

接下来n行每行m个正整数，在样例中为第二个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性b_ij。

对于100%的数据，1≤n，m，x_s，y_s，x_t，y_t，a_ij，b_ij≤100。

输出描述:

输出1行1个整数代表答案。

示例1

输入

5 5 2 4 4 3
2 1 1 3 1
1 4 2 3 1
4 4 4 2 1
3 1 1 2 4
5 1 5 5 1
5 3 4 1 3
1 1 2 2 2
2 1 4 4 5
1 1 5 3 3
3 2 1 3 3

输出

算法知识视频讲解

Python

qingci

总结：一开始看到题很慌，感觉又是自己做不出的题了。但是还是没有放弃，试着用DP的思想理了下思路，逐步分析后发现越来越像类dij算法，这才灵感如泉涌，最终得出思路：

整体是广度优先搜索的策略，每次循环使用优先级队列pq维护的当前最近的点
并使用mat来记录已经遍历的结果，防止重复遍历。
加入剪枝优化，一旦出现需要的结果立刻跳出循环。

最终时间复杂度为nlogn量级，其中n为图中需遍历的点数，n小于等于 $10^4$

n, m, xs, ys, xt, yt = map(int, input().split())
a, b = [], []
for i in range(n):
 a.append(list(map(int, input().split())))
for i in range(n):
 b.append(list(map(int, input().split())))

# 准备工作
xt, yt = xt-1, yt-1
import heapq
pq = [(0, xs-1, ys-1)]
mat = [[-1]*m for i in range(n)]


# 用于计算对于当前时间当前十字路口那个方向可以通行，
# 同时返回去另一个方向需要等待的时间
def rule(t, i, j):
 ax, bx = a[i][j], b[i][j]
 t = t % (ax + bx)
 if t < ax:
     return True, ax - t
 else:
     return False, ax + bx - t



while pq:
 min_t, i, j = heapq.heappop(pq)
 if mat[i][j] != -1:
     continue
 mat[i][j] = min_t
 if i == xt and j == yt:
     ans = min_t
     break
 direc, t_w = rule(min_t, i, j)
 for step in [1, -1]:
     ni, nj = i + step, j + step
     if 0 <= nj < m:
         heapq.heappush(pq, (min_t + 1 + (t_w if direc else 0), i, nj))
     if 0 <= ni < n:
         heapq.heappush(pq, (min_t + 1 + (0 if direc else t_w), ni, j))
print(ans)

编辑于 2021-06-23 11:47:48 回复(0)

q1w2ertyu

BFS + 优先级队列<time, x, y > ，同时用dp[N][M][2] 记录到达 X,Y 时，最早的行可移动时间和列可移动时间。不用考虑等待的问题，等待一定不是最优的。

开始时， {0， XS, YS }入列，每次从队列弹出一个位置x, y ，如果是目标点，直接返回记录的time，否则 time 一定是到达该位置最早的时间，根据要求计算从该点出发能上下访问或左右访问的最小时间，分别放到dp[x][y][0]与dp[x][y][1]里，之后如果还有访问到x，y的就直接pass了，因为肯定不是最优

优先级队列每个元素最多进入一次，出去一次。复杂度MNlog(MN);

#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>> ma(n+1,vector<int>(m+1));
    vector<vector<int>> mb(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ma[i][j] ;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mb[i][j] ;
        }
    }
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(m+1,vector<int>(2,-1)));
    priority_queue< vector<int>,vector< vector<int>>,greater< vector<int>>> q;
    q.push({0,xs,ys});
    while(!q.empty()){
        int time = q.top()[0];
        int x = q.top()[1];
        int y = q.top()[2];
        q.pop();
        if(dp[x][y][0]>=0 ) continue;
        if(x ==xt && y==yt){
            printf("%d",time);
            return 0;
        }
        if(time % (ma[x][y]+mb[x][y]) < ma[x][y] ){
            dp[x][y][0] = time;
            dp[x][y][1] = time + (ma[x][y]  -  time % (ma[x][y]+mb[x][y])) ;
        }
        else{
            dp[x][y][0] = time + (ma[x][y]+ mb[x][y]  -  time % (ma[x][y]+ mb[x][y])) ;
            dp[x][y][1] = time;
        }
        if(x-1>=1)q.push({dp[x][y][0]+1 , x-1, y});
        if(x+1 <=n)q.push({dp[x][y][0]+1 , x+1, y});
        if(y-1>=1)q.push({dp[x][y][1]+1 , x, y-1});
        if(y+1 <=m)q.push({dp[x][y][1]+1 , x, y+1});
    }
}

编辑于 2022-04-01 22:02:32 回复(1)

10185101281

最短路问题。Dijkstra 求解，复杂度 O(nm log(nm))。

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

#define pb push_back
#define pii pair<int,int>
#define fir first
#define sec second
#define ll long long
#define plii pair<ll, pii>

const int N = 1e2+10;

int a[N][N], b[N][N];
int vis[N][N];
ll d[N][N];
ll calc1(pii p, int tm){
    int mod = a[p.fir][p.sec] + b[p.fir][p.sec];
    int x = tm/mod;
    int y = tm%mod;
    if(y < a[p.fir][p.sec]) return tm;
    else return tm + (mod-y);
}
ll calc2(pii p, int tm){
    int mod = a[p.fir][p.sec] + b[p.fir][p.sec];
    int x = tm/mod;
    int y = tm%mod;
    if(y >= a[p.fir][p.sec]) return tm;
    else return tm + (a[p.fir][p.sec]-y);
}
priority_queue<plii> q;
int dx[4]{-1,1,0,0};
int dy[4]{0,0,-1,1};
int n, m;
int valid(pii p){
    return p.fir>=1 && p.fir<=n && p.sec>=1 && p.sec<=m;
}
ll dijkstra(pii s,pii t){
    memset(vis,0, sizeof(vis));
    memset(d,0x3f, sizeof(d));
    d[s.fir][s.sec] = 0;
    q.push(plii{0, s});
    while(!q.empty()){
        pii x = q.top().sec; q.pop();
        if(x == t){
            return d[x.fir][x.sec];
        }
        for(int i=0; i<2; i++){
            pii y = pii{x.fir+dx[i], x.sec+dy[i]};
            if(!valid(y)) continue;
            ll nt = calc1(x, d[x.fir][x.sec])+1;
            if(nt < d[y.fir][y.sec]){
                d[y.fir][y.sec] = nt;
                q.push(plii{-nt,y});
            }
        }
        for(int i=2; i<4; i++){
            pii y = pii{x.fir+dx[i], x.sec+dy[i]};
            if(!valid(y)) continue;
            ll nt = calc2(x, d[x.fir][x.sec])+1;
            if(nt < d[y.fir][y.sec]){
                d[y.fir][y.sec] = nt;
                q.push(plii{-nt,y});
            }
        }
    }
    return d[t.fir][t.sec];
}
int main(){
    pii s, t;
    scanf("%d%d %d%d %d%d",&n,&m,&s.fir,&s.sec,&t.fir,&t.sec);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&b[i][j]);
        }
    }
    printf("%lld\n",dijkstra(s,t));
    return 0;
}

发表于 2022-02-25 20:53:16 回复(0)

pein531

使用BFS进行求解，每个时刻都对可能移动的方向进行尝试，将下一个时刻可能到达的位置放入到一个队列中。但是在移动的过程中需要注意：由于移动受到所处时间段的限制，有可能为了花费更少的时间，本时刻决定不移动，等到下一时刻往更高效的方向进行移动。在这种情况下，下一个时刻仍然在现在的位置。而时间对于移动操作的约数，可以这么来表征：

(1) 对于区间[k*a_ij+k*b_ij, (k+1)*a_ij+k*b_ij)，左端点是a_ij+b_ij的整数倍，右端点是一个开区间，比左端点多了不到aij，因此当时刻除以a_ij+b_ij的余数小于a_ij时，所处的时刻应该满足这个约束。

(2) 对于区间[(k+1)*a_ij+k*b_ij, (k+1)*a_ij+(k+1)*b_ij)，紧邻(1)中区间的右侧，所以a_ij<=余数<a_ij+b_ij时就是这种情况。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

class Node {
    public int x;
    public int y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int n, m, xs, ys, xt, yt;
    static int[][] a, b;             // 十字路口的属性
    static boolean[][] visited;      // 节点是否已经被走过
    static int[] direction = new int[]{0, -1, 1};   // 移动方向
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        n = Integer.parseInt(params[0]);
        m = Integer.parseInt(params[1]);
        xs = Integer.parseInt(params[2]);
        ys = Integer.parseInt(params[3]);
        xt = Integer.parseInt(params[4]);
        yt = Integer.parseInt(params[5]);
        a = new int[n + 1][m + 1];
        b = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1];
        for(int i = 1; i <= n; i++){
            params = br.readLine().trim().split(" ");
            for(int j = 1; j <= m; j++)
                a[i][j] = Integer.parseInt(params[j - 1]);
        }
        for(int i = 1; i <= n; i++){
            params = br.readLine().trim().split(" ");
            for(int j = 1; j <= m; j++)
                b[i][j] = Integer.parseInt(params[j - 1]);
        }
        int cost = 0;   // 初始化花费的时间
        visited[xs][ys] = true;
        System.out.println(bfs(cost));
    }
    
    private static int bfs(int cost) {
        // 用于存储同一时间点可能到达的节点
        Queue<Node> queue = new LinkedList<>();
        // 先把起点加入队列
        queue.offer(new Node(xs, ys));
        while(!queue.isEmpty()){
            int len = queue.size();   // 当前时刻有len个可能的位置
            while(len-- > 0){
                Node cur = queue.poll();
                // 找到了小团，直接返回耗时
                if(cur.x == xt && cur.y == yt) return cost;
                // 在当前位置尝试移动
                for(int j = 0; j < direction.length; j++){
                    int remainder = cost % (a[cur.x][cur.y] + b[cur.x][cur.y]);
                    int x = cur.x, y = cur.y;
                    if(remainder < a[x][y]){
                        // 时间处于[k*aij+k*bij), (k+1)*aij+k*bij)
                        x += direction[j];
                    }else{
                        // 时间处于[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij)
                        y += direction[j];
                    }
                    // 移动位置不合法
                    if(x < 1 || x > n || y < 1 || y > m) continue;
                    // 如果下一个位置还没有走过或者当前时刻不进行移动，就往队列中添加节点
                    if(!visited[x][y] || j == 0){
                        queue.offer(new Node(x, y));
                        visited[x][y] = true;
                    }
                }
            }
            cost ++;
        }
        return cost;
    }
}

编辑于 2022-01-21 18:02:23 回复(5)

何为简

迭代, 每次刷新可以到达的所有点，直到目标点可达

n, m, xs, ys, xt, yt = map(int, input().split())
a, b = [], []
for i in range(n):
    a.append(list(map(int, input().split())))
for i in range(n):
    b.append(list(map(int, input().split())))

dp = [[None]*m for _ in range(n)]#到达i,j的时间
dp[xs-1][ys-1] = 0
t = 0
direc = [[1,0],[-1,0],[0,1],[0,-1]]
def BABA(x, y, t):
    c = a[x][y] + b[x][y]
    mod = t % c
    if mod < a[x][y]:
        return 0,1#上下
    else:
        return 2,3#左右
while True:
    for i in range(n):
        for j in range(m):
            if dp[i][j] != None and dp[i][j] <= t:
                baba = BABA(i, j, t)#当前节点可行方向
                for d in baba:
                    dx, dy = direc[d]
                    x, y = i + dx, j + dy
                    if x >= 0 and x < n and y >= 0 and y < m:
                        if dp[x][y] != None:
                            dp[x][y] == min(dp[x][y], t + 1)
                        else:
                            dp[x][y] = t + 1
    t += 1
    if dp[xt-1][yt-1] != None:
        break
print(dp[xt-1][yt-1])

发表于 2022-05-27 22:40:01 回复(1)

牛客231203952号

n, m, xs, ys, xt, yt = map(int, input().split(' '))
prop_a = []
prop_b = []
xs -= 1
xt -= 1
ys -= 1
yt -= 1
visited = [[float('inf')] * m for _ in range(n)]
visited[xs][ys] = 0
for _ in range(n):
    prop_a.append(list(map(int, input().split(' '))))
for _ in range(n):
    prop_b.append(list(map(int, input().split(' '))))

queue = [(xs, ys)]
curr_time = 0
while queue:
    len_of_queue = len(queue)
    for _ in range(len_of_queue):
        require_explore = False
        x, y = queue.pop(0)
        
        if curr_time % (prop_a[x][y] + prop_b[x][y]) < prop_a[x][y]:
            # allow move row
            if x - 1 >= 0:
                if curr_time + 1 < visited[x - 1][y]:
                    visited[x - 1][y] = curr_time + 1
                    queue.append((x - 1, y))
            if x + 1 < n:
                if curr_time + 1 < visited[x + 1][y]:
                    visited[x + 1][y] = curr_time + 1
                    queue.append((x + 1, y))
            if y - 1 >= 0 and visited[x][y - 1] > curr_time + 1:
                require_explore = True
            if y + 1 < m and visited[x][y + 1] > curr_time + 1:
                require_explore = True
        else:
            # allow move col
            if y - 1 >= 0:
                if curr_time + 1 < visited[x][y - 1]:
                    visited[x][y - 1] = curr_time + 1
                    queue.append((x, y - 1))
            if y + 1 < m:
                if curr_time + 1 < visited[x][y + 1]:
                    visited[x][y + 1] = curr_time + 1
                    queue.append((x, y + 1))
            if x - 1 >= 0 and visited[x - 1][y] > curr_time + 1:
                require_explore = True
            if x + 1 < n and visited[x + 1][y] > curr_time + 1:
                require_explore = True
        if require_explore:
            queue.append((x, y))
    queue = list(set(queue))
    curr_time += 1

print(visited[xt][yt])

发表于 2022-08-12 23:39:18 回复(0)

狠人镇居民1111号

//dijsktra + 优先队列

import java.util.*;

public classMain{

public static void main(String[] args){

Scanner sc = newScanner(System.in);

intn = sc.nextInt();

intm = sc.nextInt();

intx0 = sc.nextInt();

x0--;

inty0 = sc.nextInt();

y0--;

intx = sc.nextInt();

x--;

inty = sc.nextInt();

y--;

int[][] a = newint[n][m];

int[][] b = newint[n][m];

for(inti = 0; i < n; i++){

for(intj = 0; j < m; j++){

a[i][j] = sc.nextInt();

}

for(inti = 0; i < n; i++){

for(intj = 0; j < m; j++){

b[i][j] = sc.nextInt();

}

boolean[][] visited = newboolean[n][m];

int[][] time = newint[n][m];

for(inti = 0; i < n; i++){

Arrays.fill(time[i], Integer.MAX_VALUE);

}

PriorityQueue<int[]> pq = newPriorityQueue<>((o1, o2) -> time[o1[0]][o1[1]] - time[o2[0]][o2[1]]);

time[x0][y0] = 0;

intt = 0;

int[] directs = {-1,1};

pq.offer(newint[]{x0,y0});

while(!pq.isEmpty()){

int[] cur = pq.poll();

intcurx = cur[0], cury = cur[1];

t = time[curx][cury];

visited[curx][cury] = true;

if(curx == x && cury == y){

System.out.println(time[x][y]);

return;

}

//根据t判断当前可以走的节点，可以被松弛的对象

if(t % (a[curx][cury] + b[curx][cury]) >= a[curx][cury]){

//走列

for(inti = 0; i < 2; i++){

if(cury + directs[i] < 0|| cury + directs[i] >= m){

continue;

}

if(!visited[curx][cury + directs[i]]){

if(time[curx][cury] + 1< time[curx][cury + directs[i]]){

time[curx][cury + directs[i]] = time[curx][cury] + 1;

pq.offer(newint[]{curx, cury + directs[i]});

}

}else{

//走行

for(inti = 0; i < 2; i++){

if(curx + directs[i] < 0|| curx + directs[i] >= n){

continue;

}

if(!visited[curx + directs[i]][cury]){

if(time[curx][cury] + 1< time[curx + directs[i]][cury]){

time[curx + directs[i]][cury] = time[curx][cury] + 1;

pq.offer(newint[]{curx + directs[i], cury});

}

//不走

time[curx][cury]++;

pq.offer(newint[]{curx, cury});

}

发表于 2022-07-21 17:15:03 回复(0)

SparkElf

代码挺对称的还算漂亮

#include <bits/stdc++.h>
using namespace std;
constexpr unsigned N = 1e3 + 1;
int a[N][N], b[N][N];
bool visitedI[N][N];//广搜用visited
bool visitedJ[N][N];
struct Node {
    int i, j, k;
    Node(int i, int j, int k) :i(i), j(j), k(k) {}
    bool operator>(const Node& b) const {//注意参数，参数加const，外面也要加const
        return this->k > b.k;
    }
    bool operator<(const Node& b)const {
        return this->k < b.k;
    }
    bool isWalkVertical() const {

        return  k % b[i][j] < a[i][j];//优化 注意隐含b>a
    }
};
int solve(int n, int m, int x1, int y1, int x2, int y2) {
    priority_queue<Node, vector<Node>, greater<Node>>q;
    q.push(Node(x1, y1, 0));
    while (not q.empty())
    {
        Node cur = q.top();
        q.pop();//这里不能用const Node&，因为push后会改变top，所以必须复制。
        if (cur.i == x2 && cur.j == y2)return cur.k;
        int newk = cur.k + 1;

        if (cur.isWalkVertical()) {
            if (not visitedI[cur.i][cur.j]) {
                visitedI[cur.i][cur.j] = true;
                if (cur.i - 1 >= 0)q.push(Node(cur.i - 1, cur.j, newk));
                if (cur.i + 1 < n)q.push(Node(cur.i + 1, cur.j, newk));
            }
            if (not visitedJ[cur.i][cur.j])q.push(Node(cur.i, cur.j, cur.k + a[cur.i][cur.j] - cur.k % b[cur.i][cur.j]));//如果水平没走过，等待
        }
        else {
            if (not visitedJ[cur.i][cur.j]) {
                visitedJ[cur.i][cur.j] = true;
                if (cur.j - 1 >= 0)q.push(Node(cur.i, cur.j - 1, newk));
                if (cur.j + 1 < m)q.push(Node(cur.i, cur.j + 1, newk));
            }
            if (not visitedI[cur.i][cur.j])q.push(Node(cur.i, cur.j, cur.k + b[cur.i][cur.j] - cur.k % b[cur.i][cur.j]));
        }
    }
    return 0;
}
int main() {
    int n, m, x1, y1, x2, y2;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    for (int i = 0; i < n; i++)
        for (int j = 0;j < m;j++)
            cin >> a[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0;j < m;j++)
        {
            cin >> b[i][j];
            b[i][j] += a[i][j];//见优化
        }
    cout << solve(n, m, x1 - 1, y1 - 1, x2 - 1, y2 - 1) << endl;

    return 0;
}
/**
 *
3 3 1 2 2 1
1 2 3
3 5 9
2 3 1
1 2 3
5 6 2
1 1 1

5

 **/

发表于 2022-04-04 15:06:07 回复(0)

牛客444127117号

用BFS写。DFS会超时

发表于 2022-03-17 11:04:49 回复(0)

牛客681574814号

相当于BFS吧，用个临时集合存储到达的边界点。每个循环时间+1，不断的向其中添加点。

//
//  15.cpp
//  练习
//
//  Created by Ekko on 2021/9/13.
//

#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
int main(){
    int n, m, xs, ys, xt, yt;
    cin >> n >> m >> xs >> ys >> xt >> yt;
    --xs;
    --ys;
    --xt;
    --yt;
    int a[n][m];
    int b[n][m];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> a[i][j];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> b[i][j];
    unordered_set<int> s, s1;
    s.emplace(xs * 100 + ys);
    int time = 0;
    s1.emplace(xs * 100 + ys);
    int flag;
    while(true){
        for(auto x : s1){
            flag = 0;
            int xx = x / 100;
            int yy = x % 100;
            if(xx > 0 && s.count(x - 100) == 0)
                flag = 1;
            if(xx < n - 1 && s.count(x + 100) == 0)
                flag = 1;
            if(yy > 0 && s.count(x - 1) == 0)
                flag = 1;
            if(yy < m - 1 && s.count(x + 1) == 0)
                flag = 1;
            if(flag == 0)
                s1.erase(x);
        }
        unordered_set<int > tmp;
        for(auto x : s1){
            int xx = x / 100;
            int yy = x % 100;
            if(time % (a[xx][yy] + b[xx][yy]) < a[xx][yy]){
                if(xx + 1 < n && s.count(x + 100) == 0){
                    tmp.emplace(x + 100);
                    s.emplace(x + 100);
                }
                
                if(xx > 0 && s.count(x - 100) == 0){
                    tmp.emplace(x - 100);
                    s.emplace(x - 100);
                }
            }
            else{
                if(yy + 1 < m && s.count(x + 1) == 0){
                    tmp.emplace(x + 1);
                    s.emplace(x + 1);
                }
                if(yy > 0 && s.count(x - 1) == 0){
                    tmp.emplace(x - 1);
                    s.emplace(x - 1);
                }
            }
        }
        for(auto x : tmp)
            s1.emplace(x);
        if(s.count(xt * 100 + yt))
            break;
        ++time;
    }
    if(xs * 100 + ys == xt * 100 + yt)
        cout << 0;
    else
        cout << time + 1;
}

发表于 2021-09-14 15:36:41 回复(0)

JCoder

简单的SPFA 就行了也不用堆优化，也不用判断其他杂七杂八的东西

只需要对下面的情况进行判断：

dis[now.x][now.y] + time < dis[next.x][next.y]

如果成立则将 next 重新放入队列

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

struct Point {
    int x, y;
} st, ed;

int n, m, a[105][105], b[105][105], dis[105][105];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int canMove(int x, int y, int d, int dir) {
    int nowTime = d % (a[x][y] + b[x][y]);
    if (dir < 2) {
        if (nowTime < a[x][y]) {
            return 0;
        }
        else {
            return a[x][y] + b[x][y] - nowTime;
        }
    }
    else {

        if (nowTime < a[x][y] + b[x][y] && nowTime >= a[x][y]) {
            return 0;
        }
        else {
            return a[x][y] - nowTime;
        }
    }
}

void spfa() {
    queue<Point> q;
    q.push(st);
    memset(dis, 0x3f3f3f3f, sizeof dis);
    dis[st.x][st.y] = 0;
    while (!q.empty()) {
        Point node = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            Point next;
            next.x = node.x + dir[i][0];
            next.y = node.y + dir[i][1];
            if (next.x < 1 || next.x > n || next.y < 1 || next.y > m) {
                continue;
            }
            int p = canMove(node.x, node.y, dis[node.x][node.y], i);
            if (dis[node.x][node.y] + p + 1 < dis[next.x][next.y]) {
                dis[next.x][next.y] = dis[node.x][node.y] + p + 1;

                q.push(next);
            }
        }
    }
    printf("%d\n", dis[ed.x][ed.y]);
}

int main() {
    scanf("%d%d", &n, &m);
    scanf("%d%d", &st.x, &st.y);
    scanf("%d%d", &ed.x, &ed.y);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &b[i][j]);
        }
    }

    spfa();

    return 0;
}

发表于 2021-08-17 11:30:52 回复(0)