ZOJ 1002 Fire Net

テーマリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
タイトル:
C- Fire Net
Time Limit：2000 MS     メモリLimit：65536 KB     64 bit IO Format:%lld&%ll u
Description
Suppose that we have a square city with street.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 opengs through h h h h to shot.The four openings are facing North，East，South，and West，repectively.The will be machine shoting rough.opeach opening.
Here weassiume that a bullet is soパワフルthat can acros any distance and destroy a blockhouse on its way.On the other hand，a wall is so stroniglybuilt can stop the bulles.
The goal is to place as マンリー blockhouses in a city as possible so thatのtwo can destroy each other.A configration of blockhouse islegal provided thatのtwo blockhouss 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 conder square square cities
The follwingイメージshows five pictures of the same board.The first picture is the empty board，the second and third pictures show legal configurtions，and the fourth and fiftch pictures shares。the second picture shows one way to it，but there are several other ways.
Your task is to write a program that、given a description of a map、calculates the maximnumber of blockhouss can be plocd in the city in a legal configration.
The 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 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 upercase'X'indicating a wall.The re re no spaces in the input file.
For each test case，output one line containing the maximnumber of blockhouss that can be plocd in the city in a legal configration.
Sample input:

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

Sample out put:

5
1
5
2
4

タイトルの大意:
二つの砲台は同じレベルと同じ直線上でお互いに攻撃できます。壁があります。求めて、提供する地図の情況の下で、最大で何台の大砲を放すことができます。
問題解決の考え方：
すべての点を巡回して，配置と配置の両方を考慮して，最適解を見出した。とても簡単で深く問題を探します。
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
void bfs(int x, int y); //  
int canput(int x, int y); //                
int tot = 0, m; //               
char rec[10][10]; //    
int main()
{
  while(scanf("%d", &m) != EOF && m)
  {
    tot = 0;
  for(int i = 0; i < m; i++)
    {
    memset(rec[i], ‘\0’, sizeof(rec[i]));//   
    scanf(“%s”, rec[i]); //    
    }
    bfs(0, 0); //  
    printf(“%d
”, tot);   
  }
  return 0;
}
void bfs(int x, int y) // x         ， y            
{
  if(x == m*m) //  
  {
  if(tot < y)//    
  {
  tot = y;
  return ;
    }
  }
  else{
    int col = x/m; //           
    int row = x%m;
    if(rec[col][row] == ‘.’ && canput(col,row)) //      
    {  
    rec[col][row] = ‘0’;//       0  
    bfs(x+1, y+1); //  
    rec[col][row] = ‘.’;//       
    }
    bfs(x+1, y); //     ，    
       }
}
int canput(int col, int row) //   return1，    return0.
{
  for(int i = m-1; i >= 0; i--)
  {
    if(rec[col][i] == 'X')
    {
    break;
    }
    if(rec[col][i] == '0')
    {
    return 0;
    }
  }
  for(int i = m-1; i >= 0; i--)
  {
    if(rec[i][row] == '0')
    {
    return 0;
    }
    if(rec[i][row] == 'X')
    {
    break;
    }
  }
  return 1;
}