|
|
这题看了以后，想了一个很脑残的做法，也过了，不过用了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 .
|