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

糯米

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>
            黄色另类av| 欧美成人免费va影院高清| 国产欧美日韩激情| 亚洲人妖在线| 1000部国产精品成人观看| 久久综合一区| 99在线精品免费视频九九视| 欧美亚洲一级| 伊人影院久久| 国产欧美va欧美va香蕉在| 欧美成人一区二区三区片免费| 亚洲一区二区三区国产| 国产精品国色综合久久| 亚洲黄色免费| 久久久久久亚洲精品中文字幕 | 国产三区二区一区久久| 欧美精品一区二区在线观看| 午夜精品久久久久久久| 亚洲图片欧美午夜| 亚洲九九九在线观看| 狼狼综合久久久久综合网| 亚洲图片在线| 亚洲精品日本| 亚洲精品国产精品乱码不99按摩| 国产精品日韩在线一区| 国产乱码精品一区二区三区五月婷| 国产精品久久久久一区二区三区共| 欧美国产在线视频| 狂野欧美激情性xxxx欧美| 久久精品最新地址| 久久成人国产精品| 久久精品国产一区二区电影| 欧美不卡在线视频| 久久在线视频| 欧美精品日韩一本| 欧美日韩一区在线| 今天的高清视频免费播放成人 | 久久裸体视频| 久久综合亚洲社区| 亚洲人成网站在线播| 99视频在线精品国自产拍免费观看| 女仆av观看一区| 亚洲人成在线影院| 亚洲视频一二| 久久精品成人一区二区三区| 欧美激情第五页| 欧美日韩一区二区高清| 激情国产一区| 在线亚洲免费视频| 亚洲天堂黄色| 久久精品国产亚洲精品| 先锋资源久久| 欧美精品久久天天躁| 欧美精选一区| 国产精品美女久久| 亚洲国产精品ⅴa在线观看| 一本色道久久综合狠狠躁篇怎么玩| 久久国产精品第一页| 久久综合99re88久久爱| 亚洲图片激情小说| 蜜桃久久av| 精品成人在线| 久久久久免费观看| 中文av一区特黄| 欧美va亚洲va香蕉在线| 国产日产欧美一区| 亚洲综合激情| 卡通动漫国产精品| 欧美一区二区三区免费看| 麻豆精品在线观看| 国产精品你懂的| 99精品久久免费看蜜臀剧情介绍| 久久综合九色99| 久久xxxx精品视频| 海角社区69精品视频| 亚洲主播在线| 夜夜嗨av色一区二区不卡| 欧美精品在线视频观看| 亚洲精品美女在线| 亚洲国产欧美另类丝袜| 欧美在线视屏| 激情国产一区| 欧美肥婆在线| 免费日韩视频| 亚洲欧美日韩一区在线| 亚洲欧美日韩久久精品| 国产日本欧美一区二区三区在线| 久久精品系列| 久久久另类综合| 亚洲免费精彩视频| 亚洲国产欧美不卡在线观看| 久久亚洲一区| 中文亚洲字幕| 久久国产精品久久w女人spa| 亚洲午夜电影在线观看| 激情欧美一区二区| 91久久国产综合久久91精品网站| 噜噜噜躁狠狠躁狠狠精品视频 | 国产精品久久久久一区二区| 亚洲免费小视频| 久久久精品久久久久| 亚洲国产精品成人va在线观看| 亚洲国产成人久久综合| 欧美日韩国语| 午夜一区二区三区在线观看| 久久久久在线观看| 午夜国产欧美理论在线播放| 久久久人成影片一区二区三区观看| 亚洲狼人精品一区二区三区| 在线视频你懂得一区二区三区| 国产综合视频| 亚洲午夜电影| 亚洲一区二区在线观看视频| 久久一区二区三区国产精品| 亚洲综合精品四区| 欧美精品麻豆| 亚洲国产另类精品专区| 国精品一区二区| 亚洲美女精品久久| 亚洲另类视频| 欧美电影免费观看网站| 另类春色校园亚洲| 国产婷婷成人久久av免费高清| 一区二区欧美在线| 正在播放亚洲| 欧美日韩成人激情| 亚洲在线一区二区| 午夜精品一区二区在线观看| 国产精品一卡二| 亚洲欧美成人网| 老牛国产精品一区的观看方式| 一区二区亚洲| 欧美日韩国产美| 亚洲美女精品成人在线视频| 亚洲一区二区av电影| 国产精品免费视频观看| 宅男噜噜噜66一区二区| 欧美在线视频观看| 久久夜精品va视频免费观看| 伊人激情综合| 免费观看成人www动漫视频| 亚洲激情电影在线| 亚洲视频精品在线| 国产精品视频午夜| 乱码第一页成人| 亚洲性夜色噜噜噜7777| 欧美一区二区女人| 伊人天天综合| 国产精品日韩一区二区| 久久精品国产清高在天天线| 亚洲国产精品黑人久久久 | 久久久久青草大香线综合精品| 久久久综合精品| 亚洲国产精选| 国内精品美女av在线播放| 欧美精品三级日韩久久| 欧美一区二区在线| 亚洲性感美女99在线| 欧美大秀在线观看| 亚洲色图自拍| 亚洲免费观看高清完整版在线观看熊 | 艳女tv在线观看国产一区| 亚洲欧美中文字幕| 日韩亚洲成人av在线| 国产一区二区三区在线观看免费 | 欧美国产日韩一区二区| 中文精品视频一区二区在线观看| 久久亚洲精品视频| 亚洲综合色激情五月| 亚洲黄色性网站| 亚洲国产另类久久精品| 国产亚洲人成a一在线v站| 欧美极品aⅴ影院| 亚洲欧美日韩高清| 亚洲午夜精品久久久久久app| 精品成人一区二区三区四区| 亚洲国产成人精品女人久久久| 精品999日本| 亚洲激情综合| 亚洲伊人观看| 久久精品一二三| 裸体女人亚洲精品一区| 免费久久99精品国产自在现线| 久久久久国产一区二区三区四区| 免费一级欧美在线大片| 久久久www成人免费精品| 欧美在线免费播放| 免费成人毛片| 亚洲精品孕妇| 欧美亚洲日本网站| 久久精品亚洲热| 欧美肥婆bbw| 国产九九视频一区二区三区| 精品成人一区二区| 亚洲午夜激情网页| 亚洲综合首页| 久久综合色88| 99re热这里只有精品视频| 先锋影音国产一区| 欧美风情在线观看|