[TIOJ]1279. 填方格遊戲－續

題目連結：http://tioj.infor.org/problems/1279

從數字最大的那格一路選下來會是最佳解。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
int gx[] = {0,1,0,-1},gy[] = {1,0,-1,0};
struct Ken{
    int w,x,y;
    bool operator<(const Ken &_)const{
        return _.w > w;
    }
};
priority_queue<Ken> pq;
bitset<1005> ok[1005];
int a[1005][1005];
int main(){jizz
    int n,m;cin >> n >> m;
    lld ans = 0;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ;j < m ; j++){
            cin >> a[i][j];
            pq.push({a[i][j],i,j});
            ans += a[i][j];
        }
    }
    while(!pq.empty()){
        Ken t = pq.top();
        pq.pop();
        for(int i = 0 ; i < 4; i++){
            if(t.x+gx[i] >= 0 && t.x+gx[i] < n && t.y+gy[i] >= 0 && t.y+gy[i] < m && ok[t.x+gx[i]][t.y+gy[i]]){
                ans += a[t.x+gx[i]][t.y+gy[i]];
            }
        }
        ok[t.x][t.y] = 1;
    }
    cout << ans << endl;
    return 0;
}