poj 1321 棋盘问题

 
我把所有的棋盘区域记下来,这一只要搜索这些区域即可。

不过这样貌似还没有直接按行搜索快。失败

#include<iostream>
using namespace std;
char map[10][10];
int f[10][10],n,k,ans,num_chess;
struct type
{
       
int x,y;
}chess[
65];
bool check(int i, int j)//check if it is possible to put it at (i,j)
{
    
for(int k=1; k<=n; k++)  
            
if(f[i][k]&&k!=j)return false;
    
for(int k=1; k<=n; k++)
            
if(f[k][j]&&k!=i)return false;
    
return true;
}

void dfs(int cnt, int numchess )

     
if(cnt==k){ ans++return ; }
     
if(numchess>num_chess)return ;
     
int x=chess[numchess].x,y=chess[numchess].y;
     
     
if(check(x,y))
     {
      f[x][y]
=1;
      dfs(cnt
+1,numchess+1);
     } 
     
     f[x][y]
=0;
     dfs(cnt, numchess
+1);
}

int main()
{
    
while(cin>>n>>k)
    {
         
if(n==-1 && k==-1)break;
         memset(map,
0,sizeof map);
         memset(f,
0,sizeof f);
         ans
=0;
         num_chess
=0;
         
for(int i=1; i<=n; i++)
         
for(int j=1; j<=n; j++)
               {
                         cin
>>map[i][j];
                         
if(map[i][j]=='#')
                         {
                                           num_chess
++;
                                           chess[num_chess].x
=i; chess[num_chess].y=j; 
                         }
               }
         dfs(
0,1);
         cout
<<ans<<endl;
    }
    
    system(
"pause");
    
return 0;
}

posted on 2010-08-19 10:31 田兵 阅读(232) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜