TIOJ 1279 填方格遊戲

http://tioj.infor.org/problems/1279

好久沒更新啦....最近都在努力的衝北市賽(?
雖然現在也還在努力就是了 不過還是先跑來更新了

為了要讓數字越大的格子被算到的次數最高
所以就優先圈大數字的
然後可以發現如果有一坨一樣大的相鄰 不管怎麼圈的順序都一樣(因為是算相鄰邊的個數)
所以就開個priority queue就好

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include<bits/stdc++.h> #define ll long long using namespace std; int n,m; struct node{ int x,y,v; friend bool operator <(const node &l,const node &r){ return l.v<r.v; } }; priority_queue<node,vector<node>,less<node>> pq; int a[1005][1005]; bool sec[1005][1005]; ll ans; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>m>>n; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; pq.push({i,j,a[i][j]}); } } while(pq.size()){ node tmp = pq.top(); pq.pop(); int x=tmp.x,y=tmp.y,v=tmp.v; // cout<<x<<" "<<y<<endl; sec[x][y]=1; if(sec[x+1][y]){ ans+=a[x+1][y]; } if(sec[x-1][y]){ ans+=a[x-1][y]; } if(sec[x][y+1]){ ans+=a[x][y+1]; } if(sec[x][y-1]){ ans+=a[x][y-1]; } ans+=v; } cout<<ans<<endl; }