Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1002K-FireNet-ZJU
发信站: 哈工大紫丁香 (2002年10月05日22:31:05 星期六), 站内信件

这个题目用回溯就行了，作简单的剪枝

#include "iostream.h"
int test(char* p,int N,int pos)
{
    int i;
    for(i=1;i<=pos%N;i++)
        if(p[pos-i]==-1) break;
        else if(p[pos-i]==1)    return 0;
    for(i=1;i<=pos/N;i++)
        if(p[pos-i*N]==-1) break;
        else if(p[pos-i*N]==1)  return 0;
    return 1;
}
int place(char* p,int N,int pos,int total,int & max)
{
    if(pos>=N*N)
    {
        if(total>max)max=total;
        return 0;
    }
    if(p[pos]==0)
    if(test(p,N,pos)==1)
    {
        p[pos]=1;
        place(p,N,pos+1,total+1,max);
        p[pos]=0;
    }
    place(p,N,pos+1,total,max);
    return 0;
}
int main(int argc, char* argv[])
{
    int N,i,max;
    char * p;
    cin>>N;
    while(N>0)
    {
        p=new char[N*N];
        for(i=0;i<N*N;i++)
        {
            cin>>p[i];
            if(p[i]=='X') p[i]=-1; else p[i]=0;
        }
        max=0;
        place(p,N,0,0,max);
        cout<<max<<endl;
        delete[] p;
        cin>>N;
    }
    return 0;
} 
--
４、如果你觉得老师很凶，那么等你有了老板就知道了，

老板是没有工作任期保障的。

                                   ——比尔·盖茨

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.231]