admin管理员组

文章数量:829171

攻城掠地(优先队列)

题目描述
今天LZY攻城小分队出动了,他们需要在尽可能短的时间内攻占敌人的大本营。战场是一个n * m的二维网格,LZY小分队初始在(0,0)点,敌军大本营在( n -1 ,m - 1)点
每个点上有一个对应的数字代表LZY小分队攻占这个据点需要耗费的时间,现在作为LZY小分队的指挥官,你需要指定一条合适的路线,使LZY小分队能用最短的时间攻占敌人大本营。
输入
测试样例由多组测试数据组成。每组测试数据第一行输入两个正整数n , m ( 1 <= n,m <= 100)
接下来输入n * m 个数字 ,每个数字不超过 500
输出
输出LZY小分队攻占敌人大本营所需要的最短时间
样例输入 Copy
3 3
1 2 3
1 2 3
1 2 3
样例输出 Copy
8

  • 题意从起点到终点的最短路径
  • 用dp和优先队列都可以
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[105][105];
int v[105][105];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
struct q1{int x, y, ans;
};
struct cmp{bool operator() (q1 &p1, q1 &p2){return p1.ans > p2.ans;}
};
int bfs(){priority_queue<q1,vector<q1>,cmp> p;p.push({1,1,a[1][1]});v[1][1] = 1;while(!p.empty()) {int x = p.top().x;int y = p.top().y;int ans = p.top().ans;if(x == n && y == m)return ans;p.pop();for(int i = 0; i < 4; i ++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(tx < 1 || ty < 1 || tx > n || ty > m)continue;if(v[tx][ty] == 1)continue;v[tx][ty] = 1;p.push({tx,ty,ans + a[tx][ty]});}}
}
int main(){ios::sync_with_stdio(false);while(cin >> n >> m){memset(a,0,sizeof(a));memset(v,0,sizeof(v));for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin >> a[i][j];cout << bfs() << endl;}return 0;
} 

本文标签: 攻城掠地(优先队列)