NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 B. 踩地雷回來了

作者 主題: NPSC 2005 高中組 決賽 B. 踩地雷回來了  (閱讀 2098 次)

qwqw

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
NPSC 2005 高中組 決賽 B. 踩地雷回來了
« 於: 八月 09, 2010, 08:38:51 pm »

※想法:因為想不到任何演算法可以適用(我還太嫩了),所以就朝暴搜方向去想。

※解法:一開始讀入一個盤面,開始再有數字的周圍擺上符合地雷,當擺出一個合法的盤面,統計有多少的空格a,再統計有多少的地雷尚未擺放上去b,然後答案就可以加上Ca取b個(Combination;組合),加完之後,再找出下一組符合的盤面,直到全部都找到後,即可輸出答案。因為有用上C(Combination;組合)的想法,使的原來的code不再TLE,不然原本的想法是暴出一種符合的盤面就加一。

註解不夠多可以提出疑問~~

代碼: [選擇]
#include <iostream>
using namespace std ;
char winmine[ 10 ][ 20 ] ;
int n , m , mine , mine_n , ans , mine_maybe[ 10 ][ 10 ] , C[ 82 ][ 82 ] , area[ 10 ][ 10 ][ 10 ][ 2 ] , dx[ 8 ] = { 1 , 1 , 1 , 0 , 0 , -1 , -1 , -1 } , dy[ 8 ] = { 1 , 0 , -1 , 1 , -1 , 1 , 0 , -1 } ;
bool mine_check[ 10 ][ 10 ] , mine_dfs[ 10 ][ 10 ] , number[ 10 ][ 10 ] , mine_ck[ 10 ][ 10 ];
void dfs1( int x , int y , int mine_m ) ;
void dfs2( int x , int y , int mine_m , int k , int i ) ;
void C_nm()
{
    int i , j ;
    for ( i = 0 ; i < 82 ; i ++ )
    {
        C[ i ][ 0 ] = 1 ;
    }
    //數字overflow沒差
    for ( i = 1 ; i < 82 ; i ++ )
    {
        for ( j = 1 ; j <= i ; j ++ )
        {
            C[ i ][ j ] = C[ i - 1 ][ j ] + C[ i - 1 ][ j - 1 ] ;
        }
    }
}
bool Ck( int x , int y )
{
    if ( x >= 0 && x < n && y >= 0 && y < m )
    {
        return true ;
    }
    return false ;
}
bool Number( char q )
{
    if ( q >= '0' && q <= '9' )
    {
        return true ;
    }
    return false ;
}
int count_ans( int mine_m )
{
    return C[ mine_n ][ mine_m ] ;
}
void dfs1( int x , int y , int mine_m )
{
    if ( mine_m < 0 )
    {
        return ;
    }
    if ( y == m )
    {
        dfs1( x + 1 , 0 , mine_m ) ;
        return ;
    }
    if ( x == n )
    {
        ans += count_ans( mine_m ) ;
        return ;
    }
    if ( mine_maybe[ x ][ y ] )
    {
        dfs2( x , y , mine_m - mine_maybe[ x ][ y ] , mine_maybe[ x ][ y ] , 1 ) ;
    }
    if ( mine_maybe[ x ][ y ] == 0 )
    {
        dfs1( x , y + 1 , mine_m ) ;
    }
}
void dfs2( int x , int y , int mine_m , int k , int i )
{
    if ( k == 0 )
    {
        dfs1( x , y + 1 , mine_m ) ;
        return ;
    }
    int k2 ;
    bool ck_dfs2 = true ;
    for (  ; i <= area[ x ][ y ][ 0 ][ 0 ] ; i ++ )
    {
ck_dfs2 = true ;
        for ( k2 = 0 ; k2 < 8 ; k2 ++ )
        {
            if ( Ck( area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] , area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ) && number[ area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] ][ area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ] )
            {
                mine_maybe[ area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] ][ area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ] -- ;
                if ( mine_maybe[ area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] ][ area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ] < 0 )
                {
                    ck_dfs2 = false ;
                }
            }
        }
        if ( ck_dfs2 )
        {
            dfs2( x , y , mine_m , k - 1 , i + 1 ) ;
        }
        for ( k2 = 0 ; k2 < 8 ; k2 ++ )
        {
            if ( Ck( area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] , area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ) && number[ area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] ][ area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ] )
            {
                mine_maybe[ area[ x ][ y ][ i ][ 0 ] + dx[ k2 ] ][ area[ x ][ y ][ i ][ 1 ] + dy[ k2 ] ] ++ ;
            }
        }
    }
}
int main ()
{
    C_nm() ;
    int t , i , j , k , k2 , emptys ;
    cin >> t ;
    while ( cin >> n >> m >> mine )
    {
        t ++ ;
        //讀入盤面
        gets( winmine[ 0 ] ) ;
        for ( i = 0 ; i < n ; i ++ )
        {
            gets( winmine[ i ] ) ;
        }
        //開始初始化陣列及變數
        ans = 0 ;
        memset( mine_ck , 0 , sizeof( mine_ck ) ) ;
        memset( area , 0 , sizeof( area ) ) ;
        memset( mine_maybe , 0 , sizeof( mine_maybe ) ) ;
        memset( mine_check , 0 , sizeof( mine_check ) ) ;
        memset( mine_dfs , 0 , sizeof( mine_dfs ) ) ;
        for ( mine_n = i = 0 ; i < n ; i ++ )
        {
            for ( j = 0 ; j < m ; j ++ )
            {
                number[ i ][ j ] = Number( winmine[ i ][ j ] ) ;
            }
        }
        for ( mine_n = i = 0 ; i < n ; i ++ )
        {
            for ( j = 0 ; j < m ; j ++ )
            {
                if ( number[ i ][ j ] == false )
                {
                    mine_n ++ ;
                    mine_check[ i ][ j ] = true ;
                }
            }
        }
        for ( i = 0 ; i < n ; i ++ )
        {
            for ( j = 0 ; j < m ; j ++ )
            {
                if ( number[ i ][ j ] )
                {
                    for ( k = 0 ; k < 8 ; k ++ )
                    {
                        if ( Ck( i + dx[ k ] , j + dy[ k ] ) && number[ i + dx[ k ] ][ j + dy[ k ] ] == false )
                        {
                            mine_maybe[ i ][ j ] = winmine[ i ][ j ] - 48 ;
                            if ( mine_dfs[ i + dx[ k ] ][ j + dy[ k ] ] == false )
                            {
                                area[ i ][ j ][ 0 ][ 0 ] ++ ;
                                area[ i ][ j ][ area[ i ][ j ][ 0 ][ 0 ] ][ 0 ] = i + dx[ k ] ;
                                area[ i ][ j ][ area[ i ][ j ][ 0 ][ 0 ] ][ 1 ] = j + dy[ k ] ;
                                mine_dfs[ i + dx[ k ] ][ j + dy[ k ] ] = true ;
                                if ( mine_check[ i + dx[ k ] ][ j + dy[ k ] ] )
                                {
                                    mine_check[ i + dx[ k ] ][ j + dy[ k ] ] = false ;
                                    mine_n -- ;
                                }
                            }
                        }
                    }
                }
            }
        }
        //開始計算答案
        dfs1( 0 , 0 , mine ) ;
        //輸出答案
        cout << ans << '\n' ;
    }
}
« 上次編輯: 九月 19, 2010, 11:49:22 am 由 qwqw »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 B. 踩地雷回來了