青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

糯米

TI DaVinci, gstreamer, ffmpeg
隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
數據加載中……

POJ 2227 The Wedding Juicer FloodFill算法

這題看了以后,想了一個很腦殘的做法,也過了,不過用了1.2s,哈哈。
后來看了一個高中生大牛寫的 Pascal 程序。
根據函數名字來看,它用的是 floodfill 算法,提交了發現居然才用了188ms。
現在高中生真太牛逼了!佩服!
同時,作為一個即將畢業的大學生,哥表示壓力很大。。
以前沒見過這個算法,看了一下,發現看不大懂,但是這樣做確實很有道理!
在網上面搜了一下關于floodfill算法的資料,發現很雜,還是看不大懂。。

算法的思想就是:
每個點都有一個水位,水位最小值為這個點的高度。
首先把邊緣一周的點加入堆,這些點的水位初始化為點的高度。
每次都取出最小水位的點,將點周圍的四個點里面,從來沒有被加入過堆的點加入堆中,如果有的點的高度比水位低,那么就更新答案。
刪除最小水位的點,然后重復上一步。直到不存在沒有被加入過堆中的點為止。

用 C 再寫了一遍,小小改動,慢了 100ms。

#include <stdio.h>

#define SIZE 332

struct heap_node {
    
int x, y;
}
;

int W, H;
int map[SIZE][SIZE], fil[SIZE][SIZE];
struct heap_node heap[SIZE * SIZE];
int heap_size, left, ans;

inline 
int cmp(struct heap_node *a, struct heap_node *b)
{
    
return fil[a->y][a->x] - fil[b->y][b->x];
}


inline 
void shift_down(int idx)
{
    
struct heap_node val = heap[idx];
    
    
while (1{
        idx 
*= 2;
        
if (idx > heap_size)
            
break;
        
if (idx + 1 <= heap_size && cmp(&heap[idx + 1], &heap[idx]) < 0)
            idx
++;
        
if (cmp(&val, &heap[idx]) <= 0)
            
break;
        heap[idx 
/ 2= heap[idx];
    }

    heap[idx 
/ 2= val;
}


inline 
void shift_up(int idx)
{
    
struct heap_node val = heap[idx];
    
    
while (1{
        
if (idx / 2 <= 0)
            
break;
        
if (cmp(&heap[idx / 2], &val) <= 0)
            
break;
        heap[idx] 
= heap[idx / 2];
        idx 
/= 2;
    }

    heap[idx] 
= val;
}


inline 
void insert(int y, int x, int f = -1)
{
    
if (y < 0 || y >= H || x < 0 || x >= W || fil[y][x])
        
return ;
    
if (map[y][x] > f)
        f 
= map[y][x];
    
else
        ans 
+= f - map[y][x];
    fil[y][x] 
= f;
    heap_size
++;
    heap[heap_size].y 
= y;
    heap[heap_size].x 
= x;
    shift_up(heap_size);
    left
--;
}


inline 
void extract()
{
    heap[
1= heap[heap_size--];
    shift_down(
1);
}


int main()
{
    
int i, j;

    freopen(
"e:\\test\\in.txt""r", stdin);

    scanf(
"%d%d"&W, &H);
    
for (i = 0; i < H; i++)
        
for (j = 0; j < W; j++)
            scanf(
"%d"&map[i][j]);
    
    left 
= W * H;
    
for (i = 0; i < H; i++{
        insert(i, 
0);
        insert(i, W 
- 1);
    }

    
for (i = 1; i < W - 1; i++{
        insert(
0, i);
        insert(H 
- 1, i);
    }


    
while (left) {
        i 
= heap[1].y;
        j 
= heap[1].x;
        extract();
        insert(i 
- 1, j, fil[i][j]);
        insert(i 
+ 1, j, fil[i][j]);
        insert(i, j 
- 1, fil[i][j]);
        insert(i, j 
+ 1, fil[i][j]);
    }


    printf(
"%d\n", ans);

    
return 0;
}


Pascal:
Pascal:
{$m $100000}{由于我是做的DFS進行FLOODFILL,所以不免開了點棧深度}

Program Gp ;

const
    maxn 
= 300 ;
    dx : array[ 
0 .. 3 ] of -1 .. 1 = ( 0 , 1 , 0 , -1 ) ;
    dy : array[ 
0 .. 3 ] of -1 .. 1 = ( 1 , 0 , -1 , 0 ) ;
    zy 
= trunc( 1e9 ) ;

type
    heaptype 
=
        record
            x , y , val : longint ;
        end ;

var
    map , f             : array[ 
0 .. maxn , 0 .. maxn ] of longint ;
    use , u             : array[ 
0 .. maxn , 0 .. maxn ] of boolean ;
    heap                : array[ 
0 .. maxn * maxn ] of heaptype ;
    n , m , ans , len   : longint ;
    cant                : boolean ;

procedure init ;
var
    i , j : longint ;
begin
    fillchar( f , 
sizeof( f ) , 0 ) ;
    readln( m , n ) ;
    
for i := 1 to n do
        
for j := 1 to m do
        begin
            read( map[ i , j ] ) ; f[ i , j ] :
= zy ;
        end ;
end ;

procedure ins( x , y , val : longint ) ;
var
    t       : heaptype ;
    i       : longint ;
begin
    t.x :
= x ; t.y := y ; t.val := val ;
    inc( len ) ; i :
= len ;
    
while ( i <> 1 ) and ( heap[ i div 2 ] . val > val ) do
    begin
        heap[ i ] :
= heap[ i div 2 ] ;
        i :
= i div 2 ;
    end ;
    heap[ i ] :
= t ;
end ;

procedure sort( ii : longint ) ;
var
    j      : longint ;
    num    : heaptype ;
begin
    num :
= heap[ ii ] ;
    j :
= ii * 2 ;
    
while j <= len do
    begin
        
if ( j < len ) and ( heap[ j ] . val > heap[ j + 1 ] . val ) then inc( j ) ;
        
if num . val > heap[ j ] . val then
        begin
            heap[ ii ] :
= heap[ j ] ;
            ii :
= j ;
            j :
= ii * 2 ;
        end 
else break ;
    end ;
    heap[ ii ] :
= num ;
end;

procedure dfs( x , y , max , deep : longint ) ;
var
    i , xx , yy : longint ;
begin
    u[ x , y ] :
= false ;
    
if ( max < f[ x , y ] ) then f[ x , y ] := max ;
    
for i := 0 to 3 do
    begin
        xx :
= x + dx[ i ] ; yy := y + dy[ i ] ;
        
if ( xx <= 0 ) or ( xx > n ) or ( yy <= 0 ) or ( yy > m ) or ( not u[ xx , yy ] ) then continue ;
        
if map[ xx , yy ] <= max then dfs( xx , yy , max , deep + 1 )
        
else begin
            
if use[ xx , yy ] then
            begin
                ins( xx , yy , map[ xx , yy ] ) ;
                use[ xx , yy ] :
= false ;
            end ;
        end ;
    end ;
end ;

procedure floodfill( x : heaptype ) ;
var
    cici , i , a , b    : longint ;
begin
    
if f[ x.x , x.y ] = zy then f[ x.x , x.y ] := map[ x.x , x.y ] ;
    dfs( x.x , x.y , f[ x.x , x.y ] , 
1 ) ;
end ;

procedure solve ;
var
    i , j       : longint ;
    now         : heaptype ;
begin
    fillchar( u , 
sizeof( u ) , true ) ;
    fillchar( use , 
sizeof( use ) , true ) ;
    len :
= 0 ;
    
for i := 1 to n do
    begin
        
if use[ i , 1 ] then ins( i , 1 , map[ i , 1 ] ) ; use[ i , 1 ] := false ; f[ i , 1 ] := map[ i , 1 ] ;
        
if use[ i , m ] then ins( i , m , map[ i , m ] ) ; use[ i , m ] := false ; f[ i , m ] := map[ i , m ] ;
    end ;
    
for i := 1 to m do
    begin
        
if use[ 1 , i ] then ins( 1 , i , map[ 1 , i ] ) ; use[ 1 , i ] := false ; f[ 1 , i ] := map[ 1 , i ] ;
        
if use[ n , i ] then ins( n , i , map[ n , i ] ) ; use[ n , i ] := false ; f[ n , i ] := map[ n , i ] ;
    end ;
    
while len > 0 do
    begin
        now :
= heap[ 1 ] ; heap[ 1 ] := heap[ len ] ;
        heap[ len ] . val :
= maxlongint ; dec( len ) ;
        sort( 
1 ) ;
        floodfill( now ) ;
    end ;
end ;

procedure print ;
var
    i , j , ans : longint ;
begin
    ans :
= 0 ;
    
for i := 1 to n do
        
for j := 1 to m do inc( ans , f[ i , j ] - map[ i , j ] ) ;
    writeln( ans ) ;
end ;

procedure main ;
begin
    init ;
    solve ;
    print ;
end ;

Begin
    main ;
end .

posted on 2010-04-06 21:35 糯米 閱讀(1016) 評論(0)  編輯 收藏 引用 所屬分類: POJ

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久亚洲精品视频| 国产日产亚洲精品| 欧美一级专区| 亚洲欧美春色| 亚洲欧美日韩一区| 亚欧成人精品| 久久综合色一综合色88| 久久亚洲风情| 欧美极品一区二区三区| 欧美日韩成人激情| 国产精品揄拍一区二区| 国色天香一区二区| 亚洲国产精品视频| 亚洲一区美女视频在线观看免费| 亚洲自拍电影| 欧美不卡高清| 亚洲三级观看| 亚洲视频在线看| 久久精品国产精品亚洲| 欧美国产日韩在线| 国产精品国产a| 亚洲国产精品视频一区| 午夜精品免费在线| 欧美1区2区| 在线综合亚洲欧美在线视频| 久久本道综合色狠狠五月| 女仆av观看一区| 国产精品一页| 亚洲伦理自拍| 久久一区二区三区国产精品| 亚洲精选中文字幕| 久久高清一区| 欧美午夜一区二区福利视频| 国产日韩欧美综合一区| 日韩一级成人av| 欧美在线观看视频| 亚洲成人在线免费| 国产精品福利av| 激情六月婷婷综合| 亚洲午夜羞羞片| 欧美高清视频一区二区| 亚洲小说春色综合另类电影| 噜噜噜躁狠狠躁狠狠精品视频| 国产精品一区二区三区四区五区| 亚洲精品永久免费| 久久永久免费| 午夜视频一区二区| 欧美午夜视频在线观看| avtt综合网| 亚洲国产成人精品久久久国产成人一区 | 玖玖在线精品| 亚洲一区精品电影| 欧美性猛交xxxx乱大交蜜桃| 亚洲精品乱码| 欧美成人在线免费视频| 久久国产精品亚洲va麻豆| 国产美女精品人人做人人爽| 亚洲网站视频| 亚洲精品日韩在线| 欧美国产91| 亚洲精品国产精品久久清纯直播 | 欧美性猛交xxxx免费看久久久| 亚洲九九精品| 91久久久久久国产精品| 免费国产自线拍一欧美视频| 亚洲高清免费在线| 亚洲成色最大综合在线| 免费成人在线观看视频| 亚洲国产天堂久久综合| 欧美大片免费看| 欧美不卡高清| 一本色道久久综合亚洲二区三区| 亚洲电影在线观看| 欧美好吊妞视频| 在线亚洲欧美专区二区| 99日韩精品| 国产精品一区久久久| 久久精品国产亚洲a| 欧美一区免费视频| 激情久久一区| 亚洲精品综合精品自拍| 欧美日韩一级片在线观看| 欧美三级欧美一级| 欧美日韩成人在线视频| 一本一道久久综合狠狠老精东影业 | 免费欧美日韩| 一本大道av伊人久久综合| 亚洲日韩成人| 国产精品一区二区黑丝| 久久综合给合久久狠狠色| 欧美在线欧美在线| 亚洲国产影院| 中文在线资源观看网站视频免费不卡 | 日韩午夜电影av| 在线中文字幕不卡| 狠狠色狠狠色综合日日五| 欧美freesex8一10精品| 欧美日本亚洲| 久久av二区| 欧美xx视频| 午夜精品区一区二区三| 久久美女性网| 亚洲欧美日韩第一区| 久久综合给合久久狠狠狠97色69| 亚洲精品欧美专区| 亚洲一区综合| 亚洲国产精品一区二区尤物区 | 日韩午夜免费视频| 国产日韩欧美一区在线| 欧美黄色成人网| 国产精品人成在线观看免费| 免费亚洲网站| 国产精品日韩精品| 亚洲第一精品夜夜躁人人躁| 国产精品视频一二| 欧美~级网站不卡| 国产精品丝袜xxxxxxx| 亚洲激情网站免费观看| 国产视频一区免费看| 亚洲精品极品| 悠悠资源网久久精品| 一区二区三区国产盗摄| 亚洲人成免费| 久久精品视频在线免费观看| 午夜精品久久| 欧美日韩网站| 亚洲欧洲日本国产| 精品成人a区在线观看| 亚洲一区二区视频在线| 99av国产精品欲麻豆| 久久久久.com| 久久久高清一区二区三区| 国产精品www| 亚洲精品乱码久久久久久| 亚洲人成毛片在线播放女女| 久久黄色级2电影| 欧美一级大片在线免费观看| 欧美日韩一区精品| 欧美综合国产精品久久丁香| 亚洲人成人一区二区三区| 精久久久久久久久久久| 欧美一区二区三区四区在线| 欧美一区二区三区视频免费播放| 欧美日韩三级一区二区| 亚洲国产另类 国产精品国产免费| 激情欧美一区二区三区| 欧美亚洲免费电影| 久久精品视频在线| 国产亚洲欧洲997久久综合| 亚洲影音先锋| 午夜亚洲一区| 国产日本欧美一区二区| 欧美在线免费视频| 另类综合日韩欧美亚洲| 一区二区三区自拍| 久久综合电影| 亚洲欧洲美洲综合色网| 亚洲一区bb| 国产亚洲欧美日韩一区二区| 久久国产精品免费一区| 亚洲狠狠丁香婷婷综合久久久| 亚洲乱码精品一二三四区日韩在线| 另类春色校园亚洲| 亚洲欧洲三级| 欧美在线啊v一区| 激情av一区| 欧美激情一区在线观看| 亚洲视频网在线直播| 久久精品在线| 91久久精品国产| 欧美手机在线视频| 欧美一进一出视频| 欧美激情视频免费观看| 一区二区三区四区国产| 国产欧美一区二区色老头| 久久久蜜桃一区二区人| 一区二区三区毛片| 国产精品另类一区| 久久精品在线观看| 亚洲片在线观看| 欧美在线观看你懂的| 亚洲国产欧美不卡在线观看| 欧美日韩亚洲在线| 久久久亚洲人| 亚洲一区二区三区在线观看视频| 国产欧美精品一区二区色综合 | 亚洲最新合集| 美女主播一区| 亚洲一本大道在线| 狠狠色狠狠色综合人人| 欧美三级第一页| 久久婷婷av| 亚洲视频一区二区免费在线观看| 老司机一区二区三区| 亚洲性图久久| 亚洲理论电影网| 激情懂色av一区av二区av| 欧美视频一区二区三区…| 久久综合色综合88| 欧美一区二区三区免费看|