首页 > 代码库 > 堡垒问题

堡垒问题

2024-07-05 10:22:20   228人阅读

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

/*
* @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;
}

 

 

 


联系
我们