數據規模很小，直接搜索即可，每次試著在可以放置的位置上放置。
以下是我的代碼：
#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxn(7);
int n,ans,map[kMaxn][kMaxn];
void getxy(int depth,int &x,int &y)
{
x=depth/n;
y=depth%n;
if(y)
x++;
if(!y)
y=n;
}
bool check(int x,int y)
{
for(int i=y-1;i>=1 && map[x][i]!=2;i--)
if(map[x][i]==1)
return false;
for(int i=y+1;i<=n && map[x][i]!=2;i++)
if(map[x][i]==1)
return false;
for(int i=x-1;i>=1 && map[i][y]!=2;i--)
if(map[i][y]==1)
return false;
for(int i=x+1;i<=n && map[i][y]!=2;i++)
if(map[i][y]==1)
return false;
return true;
}
void dfs(int depth,int now)
{
if(depth>n*n)
{
if(ans<now)
ans=now;
return;
}
int x,y;
getxy(depth,x,y);
dfs(depth+1,now);
if(!map[x][y] && check(x,y))
{
map[x][y]=1;
dfs(depth+1,now+1);
map[x][y]=0;
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(cin>>n && n)
{
cin.get();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
char t;
cin>>t;
if(t=='.')
map[i][j]=0;
else
map[i][j]=2;
}
ans=0;
dfs(1,0);
cout<<ans<<endl;
}
return 0;
}
posted on 2011-04-18 15:47
lee1r 閱讀(324)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索