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

糯米

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>
            亚洲美女91| 亚洲国产欧美另类丝袜| 在线视频精品| 韩国av一区| 欧美日韩精品在线| 日韩午夜激情av| 久久久久国产精品一区二区| 亚洲人成免费| 国产亚洲一区二区精品| 欧美视频在线观看一区| 欧美久久久久久久久久| 久久国产精品久久精品国产| 亚洲精品国产精品国产自| 国内一区二区三区| 国产亚洲欧美日韩一区二区| 国产精品久久久久久一区二区三区| 欧美黄色aa电影| 久久久99国产精品免费| 欧美在线播放| 久久婷婷国产综合国色天香| 亚洲欧美日韩人成在线播放| 亚洲日本va午夜在线电影| 亚洲国产经典视频| 欧美精品v国产精品v日韩精品 | 欧美性猛片xxxx免费看久爱| 另类激情亚洲| 欧美一区二区视频97| 久久先锋影音| 欧美日本一区| 国产精品久久一区二区三区| 国产亚洲成av人在线观看导航 | 国产精品青草综合久久久久99 | 在线免费观看一区二区三区| 亚洲第一网站| 一区二区三区偷拍| 亚洲免费影视| 久久九九国产精品| 亚洲国产福利在线| 国产精品99久久久久久久vr| 亚洲欧美另类综合偷拍| 久久夜色精品国产欧美乱极品| 欧美精品xxxxbbbb| 激情欧美丁香| 久久国产精品久久w女人spa| 亚洲国产高清在线| 亚洲国产精品传媒在线观看 | av成人免费在线| 一色屋精品视频在线观看网站| 久久精品国内一区二区三区| 国产精品欧美激情| 亚洲一级黄色片| 亚洲激情一区| 欧美激情综合| 亚洲精品在线视频观看| 亚洲国产99精品国自产| 欧美 日韩 国产一区二区在线视频| 国产一区二区三区的电影| 欧美综合国产| 久久在线观看视频| 亚洲精品在线免费观看视频| 亚洲精品久久在线| 欧美偷拍另类| 亚洲网站在线看| 午夜在线观看欧美| 亚洲电影在线看| 亚洲人成毛片在线播放| 欧美日韩国产丝袜另类| 亚洲中字在线| 久久久亚洲国产美女国产盗摄| 在线精品观看| 亚洲亚洲精品在线观看| 黄色亚洲免费| 日韩午夜在线观看视频| 国产精品亚洲а∨天堂免在线| 夜夜嗨网站十八久久| 亚洲视频一区二区| 伊大人香蕉综合8在线视| 欧美国产日韩一二三区| 亚洲国产日韩在线| 国产亚洲一级| 欧美一级一区| 能在线观看的日韩av| 亚洲一区二区成人在线观看| 老司机久久99久久精品播放免费 | 亚洲免费成人av| 亚洲激情在线观看| 99视频在线观看一区三区| 久久久99国产精品免费| 午夜欧美大尺度福利影院在线看| 免费观看成人| 欧美国产日韩亚洲一区| 亚洲电影免费观看高清完整版在线 | 欧美99久久| 国产日韩精品一区二区三区在线 | 亚洲一区二区三区四区五区黄| 美女性感视频久久久| 久久野战av| 欧美人牲a欧美精品| 久久久久欧美精品| 欧美日韩综合视频网址| 一区二区三区蜜桃网| 亚洲天堂av电影| 国产日本欧美一区二区三区在线| 亚洲视频自拍偷拍| 久久国产精品第一页| 国产丝袜美腿一区二区三区| 久久久久中文| 亚洲精选久久| 国产精品久久久久7777婷婷| 亚洲综合三区| 亚洲第一黄色网| 最新日韩在线| 久久综合99re88久久爱| 亚洲一区二区三区在线播放| 国产精品一区二区久久久久| 久久综合成人精品亚洲另类欧美| 99精品国产在热久久婷婷| 欧美诱惑福利视频| 亚洲国产一区二区三区在线播 | 亚洲黄色性网站| 欧美午夜视频一区二区| 久久艳片www.17c.com| 韩国av一区二区三区| 久久午夜精品| 欧美在线观看视频在线| 亚洲精品在线看| 韩国欧美国产1区| 国产日韩欧美另类| 国产欧美日本一区二区三区| 久久一区激情| 久久影院午夜论| 亚洲欧美视频在线观看| 亚洲国产欧美一区| 在线观看欧美日韩国产| 久久视频国产精品免费视频在线| 午夜欧美不卡精品aaaaa| 亚洲一区二区精品在线观看| 亚洲人成欧美中文字幕| 一本色道久久综合一区| 一区二区三区视频在线| 亚洲欧美三级伦理| 欧美在线短视频| 久久久精品一区二区三区| 翔田千里一区二区| avtt综合网| 亚洲风情在线资源站| 亚洲国产视频a| 午夜精品视频在线| 另类成人小视频在线| 麻豆九一精品爱看视频在线观看免费| 久久久福利视频| 亚洲高清不卡在线| 亚洲女同同性videoxma| 卡一卡二国产精品| 国产精品福利在线观看| 激情视频亚洲| 久久99伊人| 亚洲社区在线观看| 亚洲国产精品v| 牛人盗摄一区二区三区视频| 欧美日韩爆操| 亚洲伦理一区| 久久久久国产精品麻豆ai换脸| 老司机亚洲精品| 亚洲欧美国内爽妇网| 欧美四级在线| 一本色道久久综合一区| 欧美激情亚洲视频| 免费久久99精品国产| 亚洲国产mv| 日韩视频亚洲视频| 国产女精品视频网站免费| 欧美在线视频免费观看| 久久性天堂网| 欧美一级久久久| 久久亚洲综合色一区二区三区| 一本久久精品一区二区| 欧美一区二区在线视频| 日韩一区二区福利| 久久av一区| 亚洲最快最全在线视频| 久久精品国产免费观看| 夜夜嗨一区二区三区| 亚洲欧美电影院| 日韩一区二区免费看| 亚洲一区中文| 亚洲一区二区三区在线视频| 午夜视黄欧洲亚洲| 欧美日韩黄色大片| 免费在线国产精品| 国产精品羞羞答答| 亚洲免费小视频| 亚洲自拍偷拍视频| 欧美护士18xxxxhd| 久久婷婷人人澡人人喊人人爽| 国产精品你懂得| 午夜精品久久久久久久男人的天堂 | 久久精品网址| 欧美精品导航| 亚洲人体影院|