wordpress适合做什么网站/友情链接的网站有哪些
1006.堡垒问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述
城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。
输入
每个测例以一个整数n（1<=n<=4）开始，表示城堡的大小。
接下来是n行字符每行n个，‘X’表示该位置是墙，‘.’表示该位置是空格。
n等于0标志输入结束。
输出
每个测例在单独的一行输出一个整数：最多修建堡垒的个数。
#include <iostream>using namespace std;int n; //城堡大小
int a[4][4]; //城堡方格，1==墙，0==空，-1==堡垒//左上角为方格[0,0]int mcnt; //最大堡垒个数
int cnt; //当前已建堡垒个数void dfs(int m); //回溯深搜
bool ok(int i,int j); //判断方格[i,j]能否放置堡垒int main()
{cin>>n;while(n){char c;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>c;if(c=='X') //墙a[i][j]=1;else //空a[i][j]=0;}}//初始化mcnt=0;cnt=0;dfs(0);cout<<mcnt<<endl;cin>>n;}return 0;
}void dfs(int m) //判断序号为m的方格
{if(m==(n*n)){ //搜到最后一个方格if(mcnt<cnt) //更新最大值mcnt=cnt;}else{int i=m/n;int j=m%n;if(ok(i,j)){ //若方格m内可以修建堡垒a[i][j]=-1;cnt++;dfs(m+1);cnt--;a[i][j]=0;}dfs(m+1);}
}//函数功能：判断方格[i,j]内能否放置堡垒
//不能放置条件：
//1.本方格是墙
//2.本方格的上方或左方有堡垒（中间无墙相隔）
//因为是按序号顺序搜索方格，因此不必判断下方或右方（还未放置，必无堡垒）
bool ok(int i,int j)
{int x,y;if(a[i][j]==1) return false; //本方格是墙for(x=i-1,y=j;x>=0;x--){ //向上找if(a[x][y]==1) break;if(a[x][y]==-1) return false;}for(x=i,y=j-1;y>=0;y--){ //向左找if(a[x][y]==1) break;if(a[x][y]==-1) return false;}return true;
}
【后记】
1.做了几道回溯，深深感觉dfs简直就是套路，里面多半是下面这种格式：
if (m==n)
{......}
else
{.......}
2.既然算法是套路，那么麻烦主要在于如何表示数据
一般来说，方格类数据用二维数组表示，每个方格有两个名字：序号m和位置[ i , j ]
默认左上角为序号0，位置为[ 0 , 0 ]，如下图所示：
【第二版代码】（10.20重写版）
#include <iostream>using namespace std;char fort[4][4]; //城堡int n; //城堡边长int maxn; //最多城堡个数int curn; //当前已修建的城堡个数void dfs(int m); //搜索第m个格子，从0开始一行一行编号bool canbuild(int x, int y); //fort[x][y]这一格能否修建城堡int main()
{while(cin>>n&&n){//数据输入for(int i=0; i<n; i++){for(int j=0; j<n; j++){cin>>fort[i][j];}}//初始化maxn=curn=0;//算法执行dfs(0);//结果输出cout<<maxn<<endl;}return 0;
}void dfs(int m)
{if(m==n*n) //所有格子都搜完{maxn=max(maxn, curn);}else{int x=m/n; //行int y=m%n; //列if(canbuild(x, y)) //判断fort[x][y]这个格子能否修建城堡{curn++;fort[x][y]='O'; //在此处修建城堡dfs(m+1);curn--;fort[x][y]='.'; //还原}dfs(m+1);}
}bool canbuild(int x, int y) //判断fort[x][y]这个格子能否修建城堡
{if(fort[x][y]=='X') //本格是墙{return false;}for(int i=x-1; i>=0; i--) //向上搜索同列元素{if(fort[i][y]=='O') //若同列有城堡则返回false{return false;}if(fort[i][y]=='X') //遇到墙则跳出{break;}}for(int i=y-1; i>=0; i--) //向左搜索同行元素{if(fort[x][i]=='O') //若同行有城堡则返回false{return false;}if(fort[x][i]=='X') //遇到墙则跳出{break;}}return true;
}