【算法實驗二】--回溯法--堡壘問題

1006.堡壘問題

時限：1000ms 記憶體限制：10000K  總時限：3000ms

描述

城堡是一個4×4的方格，為了保衛城堡，現需要在某些格子裡修建一些堡壘。城堡中的某些格子是牆，其餘格子都是空格，堡壘隻能建在空格裡，每個堡壘都可以向上下左右四個方向射擊，如果兩個堡壘在同一行或同一列，且中間沒有牆相隔，則兩個堡壘都會把對方打掉。問對于給定的一種狀态，最多能夠修建幾個堡壘。

輸入

每個測例以一個整數n（1<=n<=4）開始，表示城堡的大小。接下來是n行字元每行n個，‘X’表示該位置是牆，‘.’表示該位置是空格。n等于0标志輸入結束。

輸出

每個測例在單獨的一行輸出一個整數：最多修建堡壘的個數。

輸入樣例

4

.X..

....

XX..

....

2

XX

.X

3

.X.

X.X

.X.

3

...

.XX

.XX

4

....

....

....

....

輸出樣例

5

1

5

2

4

解析：既然是回溯問題，肯定是套用回溯法的通用模型，即：

a[m]=0;

search(m+1);

a[m]=1;

search(m+1);

那麼這裡就出現一個問題，有的地方不能放大炮就不用進入到a[m]=1這個節點了，即剪枝問題。其他的就是簡單的回溯法了，詳見代碼：

#include<stdio.h>

#include<string.h>

int a[16],max,map[5][5];

int n;

void checkmax()

{

    int value=0;

    for(int i=0;i<n;i++)

    {

        for(int j=0;j<n;j++)

        {

            if(map[i][j]==2)

                value=value+1;

        }

    }

    if(value>max)

       max=value;            //替換max

}

int canplace(int m)

{

    int i,j,row,col;

    row=m/n;

    col=m%n;

    if(map[row][col]!=0) //如果這點是牆，則不能放置大炮

        return 0;

    else

    {//如果不是牆，則看同行同列是否有炮

        for(i=row;i>=0;i--)

        {//從目前行沿着同一列傳回檢查

            if(map[i][col]==2) //是不是大炮

                return 0;

            else if(map[i][col]==1)

                break;

        }

        for(j=col;j>=0;j--)

        {

            if(map[row][j]==2)

                 return 0;

            else if(map[row][j]==1)

                 break;

        }

        return 1;

    }

}

void search(int m)

{

    if(m>=16)//此時所有節點都已周遊完，周遊解空間數得出最大的目标值

        checkmax();

    else

    {

        int row,col;

        row=m/n;

        col=m%n;

        search(m+1);//首先不放，那麼不必管，因為最後查詢的是2，

        if(canplace(m))

        {//如果可以放，就把它放成大炮，然後可以放的話也可以選擇不放，在放完之後再另其為0不影響下次

            map[row][col]=2;

            search(m+1);

            map[row][col]=0;

        }

    }

}

int main()

{

    while(scanf("%d",&n)&&n)

    {

        memset(a,0,sizeof(a));

        memset(map,0,sizeof(map));

        max=0;

        getchar();

        char ch;

        for(int i=0;i<n;i++)

        {

            for(int j=0;j<n;j++)

            {

                scanf("%c",&ch);//存的時候如果這點是牆，存為1，反之為0

                if(ch=='.')

                    map[i][j]=0;

                else

                    map[i][j]=1;

            }

            getchar();

        }

        search(0);//從第0個節點算起，共n*n個節點

        printf("%d\n",max);

    }

}