AI Translated from Chinese

Problem: Luogu UVa439

Problem Statement

Input an m*n matrix representing a map, where 1 represents obstacles and 0 represents free space. The robot needs to move from (1,1) to (m,n) on the m*n map. Each move can go one cell in one of the four directions (up, down, left, right), and can consecutively cross at most k obstacles. Data satisfies 1 <= m, n <= 20, 0 <= k <= 20.

Analysis

First, we can confirm this is not ordinary BFS shortest path (compare: Uva 439), but the problem has an additional condition — can consecutively cross at most k obstacles. This means a 2D array alone is not enough to judge the problem conditions.

So I tried using a visit array int vis[maxn][maxn][2] to store visit status, where vis[x][y][0] represents the step count after taking one more step from this cell, and vis[x][y][1] represents the number of obstacles to cross to reach this cell. But this approach has a problem: the program cannot distinguish between reaching the same cell with different numbers of obstacles, treating them as the same route.

Simply make a small improvement: use bool vis[maxn][maxn][maxn] to store visit status, where vis[x][y][cnt] means reaching (x,y) after consecutively crossing cnt obstacles.

Use a struct to store coordinates, step count, and number of consecutive obstacles crossed, making BFS enqueue and dequeue operations convenient (since only one queue is needed).

Code

C++

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 25;
int pic[maxn][maxn];  // Input map
bool vis[maxn][maxn][maxn];  // Visit array, checking if reached a cell after consecutively crossing certain number of obstacles
const int dx[4] = {0, 1, 0, -1};  // Offsets
const int dy[4] = {1, 0, -1, 0};
int t, m, n, k;

struct Node {
    int x;
    int y;
    int step;  // Current step count
    int cnt;  // Current number of consecutive obstacles crossed
};

void read_lines() {
    cin >> m >> n >> k;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> pic[i][j];
}

bool check(int x, int y) {  // Check if out of bounds
    if (x < 1 || y < 1 || x > m || y > n) return true;
    return false;
}

int bfs(int x, int y, int k) {
    Node t = {x, y, 0, 0};
    queue<Node> q;
    q.push(t);
    while (!q.empty()) {
        t = q.front();
        if (t.x == m && t.y == n) return t.step;
        for (int i = 0; i < 4; i++) {
            int px = t.x + dx[i], py = t.y + dy[i];
            if (check(px, py)) continue;  // Out of bounds
            Node tmp = {px, py, t.step, t.cnt};  // Must use temporary variable for operations!
            if (pic[px][py]) tmp.cnt++;  // This cell is an obstacle
            else tmp.cnt = 0;  // This cell is free space
            if (tmp.cnt <= k && !vis[px][py][tmp.cnt]) {  // Consecutive obstacles <= k and not visited with this count
                tmp.step++;
                vis[px][py][tmp.cnt] = true;  // Already visited
                q.push(tmp);
            }
        }
        q.pop();
    }
    return -1;
}

int main() {
#ifdef LOCAL
    freopen("patrol_robot.in", "r", stdin);
    freopen("patrol_robot.out", "w", stdout);
#endif
    ios::sync_with_stdio(false); // Disable cin and stdin synchronization, speed up I/O
    cin.tie(0);  // Unbind cin and cout, further improve efficiency
    cout.tie(0);
    cin >> t;
    while (t--) {
        memset(vis, false, sizeof(vis));  // Remember to clear!
        read_lines();
        cout << bfs(1, 1, k) << "\n";
    }
    return 0;
}

We know that cin and cout are slower than printf and scanf, so we can speed up with some tricks:

ios::sync_with_stdio(false); // Disable cin and stdin synchronization, speed up I/O
cin.tie(0);  // Unbind cin and cout, further improve efficiency
cout.tie(0);

Using macros can make it more convenient:

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

Then you can use it directly in main function.

Special note: ios::sync_with_stdio(false) should generally not be written before freopen, as it might cause weird errors.

Python

# Redirection
# import sys
# sys.stdin = open(r'patrol_robot.in', 'r')
# sys.stdout = open(r'patrol_robot.out', 'w')

def read_lines(m):
    pic = []
    for _ in range(m):
        pic.append(list(map(int, input().split())))
    return pic

def check(x, y, m, n):
    if (x < 0 or y < 0 or x > m or y > n):
        return True
    return False

def bfs(x, y, m, n, k):
    global pic, vis
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    q = [[x, y, 0, 0]]  # Use list [x, y, step, cnt] to store state, q is queue
    while len(q):
        t = q[0]
        if t[0] == m and t[1] == n:
            return t[2]
        for i in range(4):
            px = t[0] + dx[i]
            py = t[1] + dy[i]
            if check(px, py, m, n):
                continue
            tmp = [px, py, t[2], t[3]]
            if pic[px][py]:
                tmp[3] += 1
            else:
                tmp[3] = 0
            if tmp[3] <= k and vis[px][py][tmp[3]] == False:
                tmp[2] += 1
                vis[px][py][tmp[3]] = True
                q.append(tmp)
        q.pop(0)
    return -1


for _ in range(int(input())):
    m, n = map(int, input().split())
    k = int(input())
    pic = read_lines(m)
    vis = [[[False]*21 for _ in range(n)] for _ in range(m)]
    print(bfs(0, 0, m-1, n-1, k))

Python lists generally don’t overflow like C/C++ arrays; we just need to dynamically initialize pic and vis based on m and n size.

Since indices start from 1, be careful with off-by-one errors.