cpp1002.cpp

acm答案1048,1115,1002,1915,2201,2736

#include "stdio.h"
#define max 4
#define open 0
#define shooter 1
#define wall 2
#define workload 10
int res=-1;
int num,result[max*max],map[max*max];
int Do(int,int[]);
int Judge(int []);
void main()
{
int temp[max*max],i=0,j=0,k=0,count=0,answ[workload];
char s[max+1],t;
scanf("%d",&num);
while(count<workload&&num>0)
{
for(i=0;i<num;i++)
{
scanf("%s",s);
for(j=0;j<num;j++,k++)
if(s[j]=='.')
map[k]=open;
else
map[k]=wall;
}
Do(0,temp);
answ[count]=res;
res=-1;
k=0;
count++;
scanf("%d",&num);
}
if(count<workload)
for(i=0;i<count;i++)
printf("%d\n",answ[i]);
else
printf("\nToo much work!\n");
}
int Do(int start,int temp[max*max])
{
int i=0,answer=-2;
if(start==num*num)
{
answer=Judge(temp);
if(answer>res)
{
res=answer;
for(i=0;i<num*num;i++)
result[i]=temp[i];
}
return 1;
}
else
{
if(map[start]==wall)
{
temp[start]=wall;
Do(start+1,temp);
}
else
{
temp[start]=open;// leave the place blank
Do(start+1,temp);
temp[start]=shooter;// allocate a shooter there
Do(start+1,temp);
}
}
}
int Judge(int alloc[max*max])
{
int i,j,row,count=0;
for(i=0;i<num*num;i++)
if(alloc[i]==shooter)
{
row=i/num;
for(j=i+1;j<num*row+num;j++)// judge towards right
if(alloc[j]==wall)// first meet a wall
break;
else
if(alloc[j]==shooter)// first meet another shooter
return -1;
for(j=i+num;j<num*num;j+=num)
if(alloc[j]==wall)
break;
else
if(alloc[j]==shooter)
return -1;
}
for(i=0;i<num*num;i++)
if(alloc[i]==shooter)
count++;
return count;
}