【bfs優先隊列/floodfill】POJ 2227

劉汝佳黑書P89例題，先把邊界入隊，取出最小的檢查4個方向，如果小于目前的證明可以注水，注水完後更新高度為目前高度，入隊；如果大于目前高度就直接入隊。。。是以出隊的元素都是不能注水的....黑書上說有floodfill算法，沒研究過，應該類似這樣吧

LL ans;
struct node{
    int x,y;
    int h;
    friend bool operator < (node a,node b){
        return a.h>b.h;
    }
};
int n,m;
int g[333][333];
bool vis[333][333];
priority_queue<node> pp;
int d[4][2] = {0,1,0,-1,1,0,-1,0};
void bfs(){
    int i,j;
    node cur,next;
    while(!pp.empty()){
        cur = pp.top();
        pp.pop();
        for(i=0;i<4;i++){
            int x = cur.x + d[i][0];
            int y = cur.y + d[i][1];
            if(x<0 || y<0 || x>=n || y>=m || vis[x][y])continue;
            vis[x][y] = 1;
            next.x = x,next.y = y;
            if(g[x][y]<cur.h){
                ans += cur.h-g[x][y];
                g[x][y] = cur.h;
                next.h = g[x][y];
            } else {
                next.h = g[x][y];
            }
            pp.push(next);
        }
    }
    printf("%I64d\n",ans);
}

int main(){
    while(scanf("%d%d",&m,&n) != -1){
        int i,j;
        while(!pp.empty())pp.pop();
        node tt;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                scanf("%d",&g[i][j]);
                vis[i][j] = 0;
                if(i==0 || j==0 || i==n-1 || j==m-1){
                    tt.x = i,tt.y = j,tt.h = g[i][j];
                    pp.push(tt);
                    vis[i][j] = 1;
                }
            }
        }
        ans = 0;
        bfs();
    }
    return 0;
}