首页 > 其他 > 详细

日常训练17-10-14

时间:2017-10-15 13:21:55      阅读:292      评论:0      收藏:0      [点我收藏+]

Emptying the Baltic

Kattis - emptyingbaltic
题意:问给定位置的抽水机需要排多少水。
类似最短路~
技术分享
 1 /*************************************************************************
 2     > File Name: temp.cpp
 3     > Author: yijiull 
 4     > Mail: 1147161372@qq.com 
 5     > Created Time: 2017年10月15日 星期日 09时56分36秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include <bits/stdc++.h>
10 
11 using namespace std;
12 const int maxn = 510;
13 int p[maxn][maxn], vis[maxn][maxn];
14 long long ans;
15 
16 struct Node{
17     int x, y;
18     int dep;
19     Node(int x,  int y, int dep): x(x), y(y), dep(dep){}
20     bool operator < (const Node &a)const {
21         return dep > a.dep;
22     }
23 };
24 int n, m;
25 int sx, sy;
26 
27 int d[8][2]={0, 1, 0, -1, 1, 0, 1, 1, 1, -1, -1, 0, -1, 1, -1, -1};
28 
29 int ck(int x, int y){
30     return x>=0&&x<n && y>=0&&y<m && !vis[x][y] && p[x][y] < 0;
31 }
32 
33 void bfs(){
34     priority_queue<Node> q;
35     memset(vis, 0, sizeof(vis));
36     ans = -p[sx][sy];
37     q.push(Node(sx, sy, p[sx][sy]));
38     vis[sx][sy] = 1;
39     while(!q.empty()){
40         Node now = q.top();
41         q.pop();
42         int x = now.x, y = now.y, dep = now.dep;
43         for(int i = 0; i < 8; i++){
44             int dx = x + d[i][0];
45             int dy = y + d[i][1];
46             if(ck(dx, dy)){
47                 vis[dx][dy] = 1;
48                 ans -= max(dep, p[dx][dy]);
49                 q.push(Node(dx, dy, max(p[dx][dy], dep)));
50             }
51         }
52     }
53 }
54 
55 int main(){
56     scanf("%d %d", &n, &m);
57     for(int i = 0; i < n; i++){
58         for(int j = 0; j < m; j++){
59             scanf("%d", &p[i][j]);
60         }
61     }
62     scanf("%d %d", &sx, &sy);
63     sx--; sy--;
64     bfs();
65     printf("%lld\n", ans);
66 }
View Code

 

 

日常训练17-10-14

原文:http://www.cnblogs.com/yijiull/p/7670323.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!