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

糯米

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>
            9人人澡人人爽人人精品| 亚洲一区影音先锋| 中日韩男男gay无套| 亚洲人成亚洲人成在线观看图片 | 欧美日韩亚洲网| 欧美精品久久久久久| 国产精品v亚洲精品v日韩精品| 国产精品久久久久一区二区| 国产美女精品视频| 欧美精选在线| 日韩亚洲不卡在线| 亚洲已满18点击进入久久| 欧美在线视频一区二区| 麻豆av福利av久久av| 最新亚洲一区| 一本综合久久| 久久人人爽人人爽| 欧美午夜不卡视频| 激情小说另类小说亚洲欧美| 亚洲精品女av网站| 久久国产欧美| 亚洲人成在线播放网站岛国| 欧美一区二区高清在线观看| 蜜桃av久久久亚洲精品| 欧美小视频在线观看| 在线观看国产精品淫| 亚洲欧美日韩一区二区| 欧美风情在线观看| 先锋影音国产精品| 欧美日韩亚洲在线| 亚洲人在线视频| 久久九九精品99国产精品| 亚洲国产婷婷| 久久久精品视频成人| 国产精品扒开腿做爽爽爽视频| 在线观看三级视频欧美| 性色av一区二区怡红| 亚洲人精品午夜| 久久夜色精品亚洲噜噜国产mv| 国产酒店精品激情| 亚洲欧美国产另类| 日韩小视频在线观看| 欧美大片国产精品| 亚洲国产日韩精品| 久久夜色精品国产欧美乱| 亚洲女性裸体视频| 国产精品日韩一区二区三区| 中文av字幕一区| 亚洲精品在线三区| 欧美日韩精品中文字幕| 亚洲精品久久久久中文字幕欢迎你 | 亚洲免费影院| 亚洲久久成人| 欧美激情一区二区三区成人| 伊伊综合在线| 欧美fxxxxxx另类| 久久久国产精品一区| 国产亚洲精品久久久久久| 欧美尤物一区| 欧美在线视屏| 狠狠色狠狠色综合日日五| 久久久久国产一区二区| 午夜精品久久久久久久久久久久 | 欧美一区二区三区啪啪| 亚洲国产精品女人久久久| 久久久久国产精品厨房| 国产精品自拍视频| 久久久久久久久久久一区| 欧美怡红院视频一区二区三区| 国产欧亚日韩视频| 久久久久久久999| 久久亚洲一区| 亚洲免费观看高清完整版在线观看熊 | 免费不卡在线观看av| 亚洲精品一线二线三线无人区| 欧美成人精品三级在线观看| 欧美aaaaaaaa牛牛影院| 一区二区电影免费在线观看| 一本久久a久久精品亚洲| 国产精品久久一区主播| 久久久久国产一区二区三区| 久久亚洲免费| 亚洲午夜视频在线观看| 西西裸体人体做爰大胆久久久| 在线精品亚洲一区二区| 亚洲精品视频免费| 国产午夜一区二区三区| 亚洲国产成人午夜在线一区| 欧美午夜精品| 美日韩免费视频| 欧美婷婷久久| 欧美暴力喷水在线| 欧美日韩一区二区三区视频| 欧美一站二站| 欧美成人69av| 欧美在线一二三区| 欧美丰满高潮xxxx喷水动漫| 午夜精品理论片| 免费久久久一本精品久久区| 亚洲欧美激情一区二区| 久久亚洲影音av资源网| 小处雏高清一区二区三区| 麻豆精品一区二区综合av | 亚洲欧美日韩国产| 久久一区二区三区国产精品 | 欧美国产视频在线| 国产精品麻豆va在线播放| 欧美成人综合| 国产伪娘ts一区| 99视频精品| 亚洲精品免费一二三区| 久久国产毛片| 欧美亚洲视频在线观看| 欧美国产成人在线| 久久综合导航| 国产性猛交xxxx免费看久久| 国产精品尤物| 国产一区二区三区四区三区四| 欧美a级一区二区| 国产日韩精品久久久| 夜夜嗨av色综合久久久综合网| 在线观看亚洲视频| 欧美一区影院| 欧美一区深夜视频| 国产精品久久久久免费a∨大胸| 亚洲第一区中文99精品| 1024成人网色www| 久久精品国产亚洲一区二区| 亚洲欧美成人一区二区三区| 欧美日韩精品免费看| 亚洲精品乱码久久久久久按摩观| 亚洲国产高清高潮精品美女| 久久精品欧美| 模特精品在线| 91久久精品美女高潮| 久久人人97超碰人人澡爱香蕉 | 亚洲国产精品999| 亚洲国产第一| 欧美成人免费一级人片100| 欧美18av| 亚洲人成毛片在线播放女女| 蜜桃av一区二区在线观看| 欧美国产日韩二区| 亚洲精品黄色| 欧美精品久久久久久久久久| 亚洲三级影院| 亚洲一区二区三区免费观看| 欧美日韩综合不卡| 亚洲一级免费视频| 久久久久网站| 亚洲国产天堂网精品网站| 欧美不卡一区| 亚洲午夜一区二区三区| 久久久99国产精品免费| 亚洲第一网站免费视频| 欧美精品激情在线观看| 99精品99| 久久蜜臀精品av| 日韩午夜剧场| 国产乱码精品一区二区三区忘忧草| 午夜视频久久久| 欧美福利视频一区| 亚洲午夜激情| 国产一区二区福利| 欧美高清hd18日本| 亚洲视频自拍偷拍| 久久一区中文字幕| 亚洲免费播放| 国产精品私房写真福利视频| 欧美在线观看视频| 亚洲美女诱惑| 久久久久青草大香线综合精品| 亚洲精品视频在线播放| 国产精品国产三级国产| 久久乐国产精品| 日韩视频欧美视频| 蜜臀久久久99精品久久久久久 | 亚洲深夜福利| 国内精品一区二区| 欧美日韩大片| 麻豆成人精品| 午夜在线成人av| 亚洲精品一级| 欧美国产精品日韩| 激情综合激情| 亚洲欧美另类在线观看| 欧美不卡一区| 欧美制服丝袜| 亚洲一区二区三区四区五区黄| 精品av久久久久电影| 国产精品久久久久国产精品日日| 卡一卡二国产精品| 欧美一区二区三区成人| 夜夜嗨av一区二区三区四季av | 日韩一二三区视频| 亚洲二区视频| 激情成人av在线| 国产一区视频在线看| 国产精品豆花视频| 欧美日韩精品在线|