计算二维数组坐标“岛”的重心问题

楚香饭

[Fortran] 纯文本查看 复制代码

Do i = 1 , n
  Do j = 1 , m
    if ( a(i,j) == 1 ) then
      !此时的 i j 即为坐标
    end if
  End Do
End Do

楚香饭

什么叫 把他们 -20 变到下面来？

楚香饭

这个问题可以很简单，也可以很复杂。

这取决于：
第一：整个区域内，你是否可以确定只存在一个“岛”？还是有可能有多个？
比如：
00000000000001111111100000000000
00000000000000011110000000000000
00000000000000000000000000000000
00000000110000000000000000000000
00000001111000000000000000000000
00000000000000000000000000000000
第二：岛会不会出现无限循环。
比如：
00000000000001111000000000000000
00000000000001111000000000000000
00000000001111111000000000000000
00000000000001111000000000000000
第三：岛中间是否可能出现空洞？
比如：
00000000000000000000000000000000
00000000000001111000000000000000
00000000000001111000000000000000
00000000001111001000000000000000
00000000000001111000000000000000
00000000000000000000000000000000

楚香饭

我这里有个死办法，那就是如果有上下左右的联通，则移动整个区域，直到不再联通为止。（记录下 X Y 的偏移量）
最后算出重心，再把偏移量加回去。

[Fortran] 纯文本查看 复制代码

Program www_fcode_cn
  Implicit None
  Integer , parameter :: N = 4
  Integer , parameter :: M = 4
  real :: gx , gy
  Integer :: a( M , N )
  Open( 12 , File = '文件名' )
  Read( 12 , * ) a
  Close( 12 )
  call IslandGravity( a , N , M , gx , gy )
  write(*,*) gx , gy
 
contains

  Subroutine IslandGravity( d , n , m , gx , gy )
    Integer :: n , m
    Integer :: d( m , n ) , a( m , n )
    integer :: i , j , c , iShiftX , iShiftY
    Real :: gx , gy
    Logical :: blink
    a = d !// 复制一份 a

    iShiftX = 0
    iShiftY = 0
    Do  !// 向上滚动，直到没有上下链接为止
      blink = Check_Y_Link( a , n , m )
      if ( blink ) then
        call RollUp( a , n , m )
        iShiftY = iShiftY + 1
      else
        Exit
      end if
    End Do
    Do  !// 向左滚动，直到没有左右链接为止
      blink = Check_X_Link( a , n , m )
      if ( blink ) then
        call RollLeft( a , n , m )
        iShiftX = iShiftX + 1
      else
        Exit
      end if
    End Do
    gx = 0.
    gy = 0.
    c = 0
    Do i = 1 , N
      Do j = 1 , M
        if ( a(j,i) == 1 ) then
          gx = gx + j
          gy = gy + i
          c = c + 1
        end if
      End Do
    End Do
    gx = ( gx / c ) + iShiftX !// 最后再把偏移量加上去
    if ( gx > m ) gx = gx - m
    gy = ( gy / c ) + iShiftY
    if ( gy > n ) gy = gy - n
  End Subroutine IslandGravity
  
  Subroutine RollUp( a , n , m ) !// 区域向上滚动
    Integer :: n , m
    Integer :: a( m , n ) , t( m )
    t(:) = a( : , 1 )
    a(:,1:n-1) = a(:,2:n)
    a(:,n) = t(:)
  End Subroutine RollUp
  
  Subroutine RollLeft( a , n , m ) !// 区域向左滚动
    Integer :: n , m
    Integer :: a( m , n ) , t( n )
    t(:) = a( 1 , : )
    a(1:m-1,:) = a(2:m,:)
    a(m,:) = t(:)
  End Subroutine RollLeft
  
  Logical Function Check_Y_Link( a , n , m ) !// 检查是否有上下链接
    Integer :: n , m
    Integer :: a( m , n )
    integer :: i
    Check_Y_Link = .false.
    Do i = 1 , m
      if ( ( a(i,1) == 1 ) .and. ( a(i,n) == 1 ) ) then
        Check_Y_Link = .true.
        return
      end if
    End Do
  End Function Check_Y_Link
  
  Logical Function Check_X_Link( a , n , m ) !// 检查是否有左右链接
    Integer :: n , m
    Integer :: a( m , n )
    integer :: i
    Check_X_Link = .false.
    Do i = 1 , n
      if ( ( a(1,i) == 1 ) .and. ( a(m,i) == 1 ) ) then
        Check_X_Link = .true.
        return
      end if
    End Do
  End Function Check_X_Link
  
End Program www_fcode_cn  

楚香饭

joejimming 发表于 2014-3-6 19:01
不清楚这里重心的意义为何，感觉有一点点问题：
例如：
1101

感谢楼上指正。

已增加两行代码解决这一问题

[Fortran] 纯文本查看 复制代码

 gx = ( gx / c ) + iShiftX !// 最后再把偏移量加上去
 if ( gx > m ) gx = gx - m
 gy = ( gy / c ) + iShiftY
  if ( gy > n ) gy = gy - n