首页 > 代码库 > 堡垒问题

堡垒问题

  堡垒问题是在学习递归回溯时的一个经典问题,在递归求解此类问题时,总是先判断当前状态是否行,如果可行,则试着放置一个问题的解,继续递归搜索。递归结束后之后要将状态改变回来,因为前提只是假设先放置着问题的解,之后肯定要修改回来才能保证问题解的正确性。如果忘记修改状态回来,程序肯定会出错。在搜索时,注意条件可以进行剪枝,避免不必要的递归,节约时间。最重要的是要明确递归结束条件。

/*
* @author Panoss
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<ctime>
#include<stack>
#include<queue>
#include<list>
using namespace std;
#define DBG 1
#define fori(i,a,b) for(int i = (a); i < (b); i++)
#define forie(i,a,b) for(int i = (a); i <= (b); i++)
#define ford(i,a,b) for(int i = (a); i > (b); i--)
#define forde(i,a,b) for(int i = (a); i >= (b); i--)
#define forls(i,a,b,n) for(int i = (a); i != (b); i = n[i])
#define mset(a,v) memset(a, v, sizeof(a))
#define mcpy(a,b) memcpy(a, b, sizeof(a))
#define dout DBG && cerr << __LINE__ << " >>| "
#define checkv(x) dout << #x"=" << (x) << " | "<<endl
#define checka(array,a,b) if(DBG) { \
dout<<#array"[] | " << endl; forie(i,a,b) cerr <<"["<<i<<"]="<<array[i]<<" |"<<((i-(a)+1)%5?" ":"\n"); if(((b)-(a)+1)%5) cerr<<endl; }
#define redata(T, x) T x; cin >> x
#define MIN_LD -2147483648
#define MAX_LD 2147483647
#define MIN_LLD -9223372036854775808
#define MAX_LLD 9223372036854775807
#define MAX_INF 18446744073709551615
inline int reint() { int d; scanf("%d",&d); return d; }
inline long relong() { long l; scanf("%ld",&l); return l; }
inline char rechar() { scanf(" "); return getchar(); }
inline double redouble() { double d; scanf("%lf", &d); return d; }
inline string restring() { string s; cin>>s; return s; }


int n,ans;
char a[4][4];

bool IsCanPlace(int x, int y)
{
  forde(i,x-1,0)
  {  
    if(a[i][y]==0) return false;
    if(a[i][y]==X) break;
  }
  forde(i,y-1,0)
  {
    if(a[x][i]==0) return false;
    if(a[x][i]==X) break;
  }
  return true;
}
void DFS(int k, int current_ans)
{
  if(k==n*n)
  {
    ans = max(ans,current_ans);
    return ;
  }
  else
  {
    int x = k/n;
    int y = k%n;
    if(a[x][y]==.&&IsCanPlace(x,y))
    {
      a[x][y] =0; ///先放一个堡垒
      DFS(k+1,current_ans+1);
      a[x][y] =.; ///搜索结束后再放置回来
    }
    DFS(k+1,current_ans);///搜索不放的状态
  }
}
int main()
{
  while(scanf("%d",&n)==1&&n)
  {
    fori(i,0,n)
    scanf("%s",a[i]);
    ans=0;
    DFS(0,0);
    cout<<ans<<endl;
  }
  return 0;
}