Patrol Robot UVA - 1600 BFS最短路径长

62 阅读 0 评论 41 点赞

我是靠谱客的博主苹果蛋挞，最近开发中收集的这篇文章主要介绍Patrol Robot UVA - 1600 BFS最短路径长，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题目大意：

给一个矩阵，从（1，1）走到（m，n）的最短路，"1"是障碍，不能连续穿过k个障碍。

分析：

用一个结构体，属性有x，y坐标，当前距离，可以跨越障碍数目。

然后bfs便利即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
int dir[5][5] = {{1,0},{0,1},{-1,0},{0,-1}};
struct Node
{
    int x,y,dis,step;
    Node(int _x, int _y, int _dis,  int _step):
        x(_x), y(_y), dis(_dis), step(_step) {};
};
int matrix[maxn][maxn],r,c,num;
bool vis[maxn][maxn];
int bfs() {
    queue<Node> queue1;
    queue1.push(Node(0,0,0,num));
    while(!queue1.empty()) {
        Node u = queue1.front(); queue1.pop();
        int ur = u.x, uc = u.y;
        if(ur==r-1 && uc==c-1) return u.dis;
        for(int i = 0; i < 4; i++) {
            int vr = ur+dir[i][0], vc = uc+dir[i][1];
            if(vr>=0 && vc>=0 && vr<r && vc<c) {
                if(!matrix[vr][vc] && !vis[vr][vc]) {
                    vis[vr][vc] = true;
                    queue1.push(Node(vr,vc,u.dis+1,num));
                }
                if(matrix[vr][vc]==1 && u.step>0 && !vis[vr][vc]) {
                    vis[vr][vc] = true;
                    queue1.push(Node(vr,vc,u.dis+1,u.step-1));
                }
            }
        }
    }
    return -1;
}


int main() {
    freopen("i.txt","r",stdin);
    freopen("o.txt","w",stdout);
    int n;
    cin >> n;
    while(n--) {
        memset(matrix,0,sizeof(matrix));
        memset(vis,false,sizeof(vis));
        cin >> r >> c >> num;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++)
                cin >> matrix[i][j];
        }
        cout << bfs() << endl;
    }
}

第一次用数组写的，总是wa，不知道为什么，先贴着吧。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50;
int dir[5][5] = {{1,0},{0,1},{-1,0},{0,-1}};
int matrix[maxn][maxn], dis[maxn*30+maxn], vis[maxn*30+maxn];
int jump[maxn*30+maxn];
int r,c,num;

void bfs() {
    queue<int> queue1;
    int beg = 0;
    queue1.push(beg);
    dis[beg] = 0; vis[beg] = 1;
    while(!queue1.empty()) {
        int u = queue1.front(); queue1.pop();
        int rr = u/30, cc = u%30;
        for(int i = 0; i < 4; i++) {
            int vr = rr+dir[i][0], vc = cc+dir[i][1];
            if(vr>=0 && vr<r && vc>=0 && vc<c) {
                bool flag = false;
                int v = vr*30+vc;
                if(!matrix[vr][vc]) {
                    flag = true;
                    jump[v] = num;
                }
                else if(jump[u]>0) {
                    flag = true;
                    jump[v] = jump[u]-1;
                }
                if(flag && !vis[v]) {
                    queue1.push(v);
                    vis[v] = 1;
                    dis[v] = dis[u]+1;
                }
            } 
        }
    }
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        memset(matrix, 0, sizeof(matrix));
        memset(dis, -1, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        cin >> r >> c >> num;
        for(int i = 0; i < 30*r+c; i++)
            jump[i] = num;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) 
                cin >> matrix[i][j];
        }
        bfs();
        int ed = (r-1)*30+(c-1);
        cout << dis[ed] << endl;
    }
}