【算法】算法之美—Fire Net

題目概述：Fire Net

　　Suppose  that we have a square city with straight streets. A map of a city is a square  board with n rows and n columns, each representing a street or a piece of  wall.

　　A  blockhouse is a small castle that has four openings through which to shoot. The  four openings are facing North, East, South, and West, respectively. There will  be one machine gun shooting through each opening.

　　Here we  assume that a bullet is so powerful that it can run across any distance and  destroy a blockhouse on its way. On the other hand, a wall is so strongly built  that can stop the bullets.

　　The goal  is to place as many  blockhouses in a city as possible so that no two can destroy each other. A  configuration of blockhouses is legal  provided that no two blockhouses are on the same horizontal row or vertical  column in a map unless there is at least one wall separating them. In this  problem we will consider small square cities (at most 4x4) that contain walls  through which bullets cannot run through.

　　The  following p_w_picpath shows five pictures of the same board. The first picture is the  empty board, the second and third pictures show legal configurations, and the  fourth and fifth pictures show illegal configurations. For this board, the  maximum number of blockhouses in a legal configuration is 5; the second picture  shows one way to do it, but there are several other ways.

　　Your  task is to write a program that, given a description of a map, calculates the  maximum number of blockhouses that can be placed in the city in a legal  configuration.

　　he  input file contains one or more map descriptions, followed by a line containing  the number 0 that signals the end of the file. Each map description begins with  a line containing a positive integer n that is  the size of the city; n will be  at most 4. The next n lines  each describe one row of the map, with a '.'  indicating an open space and an uppercase 'X'  indicating a wall. There are no spaces in the input file.

　　For each  test case, output one line containing the maximum number of blockhouses that can  be placed in the city in a legal configuration.

Sample  input:

4

.X..

....

XX..

2

XX

.X

3

.X.

X.X

...

.XX

Sample  output:

5

1

簡單描述

　　題是英文的，重要的語句我已經标出來了，其實題的意思很簡單：

　　在一個n*n(最大為4*4)的矩形表格中，由你指定在哪些表格不空(用"X"表示，代表wall),哪些表格是空的(用"."表示，可以建blockhouses)，現在要在空的(".")表格中寫O(建blockhouses),要求就是在水準或者豎直方向上不能有兩個O直接或間接相鄰，問最多可以寫幾個O(建blockhouses)？

題目分析

　　1、不空的表格由自己決定，即為輸入的一部分

　　2、在水準或者豎直方向上不能有兩個O直接或間接相鄰，意味着需要作周遊判斷

　　3、最多可以寫幾個O(建blockhouses)，意味着需要對所有表格進行分析

　　下面貼出源代碼，其中我對最主要的代碼都作了詳細的注釋

解題算法

 
 #include < stdio.h>       
      
 char map[4][4];       
      
 int best,n;       
      
 int CanPut(int row, int col)       
      
 /*       
      
 *檢測與前行或者與前列是否存在沖突,即原文中的       
      
 *no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them       
      
 *如果bullets cannot run through，則傳回1       
      
 *否則bullets can run through，傳回0       
      
 */       
      
 {       
      
 int i;       
      
 for (i = row - 1; i >= 0; i--)       
      
   {       
      
 if (map[i][col] == 'O') return 0;       
      
 if (map[i][col] == 'X') break;       
      
   }       
      
 for (i = col - 1; i >= 0; i--)       
      
   {       
      
 if (map[row][i] == 'O') return 0;       
      
 if (map[row][i] == 'X') break;       
      
   }       
      
 return 1;       
      
 }       
      
 void solve(int k,int tot)       
      
 /*       
      
 *calculates the maximum number of blockhouses that can be placed in the city in a legal configuration       
      
 *k表示被檢測的map單元個數       
      
 *tot表示可以放置blockhouses的個數       
      
 */       
      
 {       
      
 int x,y;       
      
 if(k==n*n)//保證整個地圖都被檢測過       
      
   {       
      
 if(tot>best)         
      
     {       
      
        best=tot;           
      
 return;         
      
     }       
      
   }       
      
 else       
      
   {       
      
     x=k/n; //先逐行進行檢測       
      
     y=k%n; //逐列進行檢測       
      
 if((map[x][y]=='.') && (CanPut(x,y) ) )//是open space，并且 bullets cannot run through       
      
     {       
      
       map[x][y]='O';//'0'表示已經檢測過并且可放置blockhouses，即将tot+1       
      
       solve(k+1,tot+1);//map[x][y]可以放置blockhouses，則從map[(k+1)/n][(k+1)%n]開始繼續檢測,即逐行進行檢測，并且tot+1       
      
       map[x][y]='.';//在恢複堆棧的時候，還原map原來的資料       
      
     }       
      
     solve(k+1,tot);//若map[k/n][k%n]存在bullets can run through，則繼續從map[(k+1)/n][(k+1)%n]開始逐行檢測       
      
   }       
      
 }       
      
 int main()       
      
 {       
      
 int i,j;       
      
   scanf("%d",&n);       
      
 while(n>0)       
      
   {       
      
 for(i=0;i< n;i++)       
      
     {       
      
 for(j=0;j< n;j++)       
      
        {       
      
            scanf("%1s",&map[i][j]);//輸入單個字元并且忽略空白       
      
        }       
      
     }       
      
     best=0;       
      
     solve(0,0);       
      
     printf("%d\n",best);       
      
     n=0;//預防scanf失敗,reset n       
      
     scanf("%d",&n);       
      
   }       
      
 return 0;       
      
 }