原创

： 火力网的c语言代码，递归调用

火力网的c语言代码，递归调用

假设我们有一个直街道广场的城市。一个城市的地图用n行n列的方形板，每一个代表一个街道或一块墙。
一个碉堡就是一个小城堡，有四个开口用以射击。四开口面朝北，东，南，西，分别。会有一个机枪射击通过每个开口。
在这里，我们假定子弹是如此强大，它可以运行在任何距离和毁灭的道路上一个碉堡。另一方面，墙是如此强烈地建成，可以阻止子弹。
其目标是把城市中的许多碉堡使没有两个可以摧毁对方。一个配置的碉堡是法律规定，没有两个碉堡是在地图上的同一行或列除非有至少一个壁分离。在这个问题中，我们会考虑小城市广场（最多4×4）包含墙壁透过子弹不能贯穿。
示例
下面的图像显示五张相同的牌。第一张照片是空板，第二和第三的照片显示法律的配置，以及第四和第五的图片显示非法配置。这个委员会，在法律结构的碉堡数目最多为5；第二张图片展示了一种方式，但也有一些其他的方法。
你的任务是写一个程序，设计一个地图，计算碉堡可以放置在城市中的法律配置的最大数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include <stdio.h>
void search(int x,int y,int sum);
int bol[4][4];//表示障碍  和  是否有碉堡
int n;
int max=0;//最大数量
int ke(int x,int y);//可以放置碉堡
main()
{
  int i,j;
  char s;
  char ss[4][4];
  while(scanf("%d",&n)!=EOF&&n!=0)
  {
  	max=0;
  	 //printf("\n");
  for(i=0;i<=n-1;i++)
  {
  	getchar(); 
  	for(j=0;j<=n-1;j++)
  	{
  		 	scanf("%c",&ss[i][j]);
  		 	if(ss[i][j]=='X')
  		 	{
  		 		bol[i][j]=-1;
			}
			else
			{
			   	bol[i][j]=0;
		    }
	}
   }
  /* printf("\n");
   for(i=0;i<=n-1;i++)
   {
	   	for(j=0;j<=n-1;j++)
	   	{
	   		printf("%c",ss[i][j]);
		}
		printf("\n");
   }*/
   
    /*for(i=0;i<=n-1;i++)
   {
	   	for(j=0;j<=n-1;j++)
	   	{
	   		printf("%2d",bol[i][j]);
		}
		printf("\n");
   }*/
   //printf("\n");
    search(0,0,0);
    printf("%d\n",max);
  }
 
}
void search(int x,int y,int sum)
{
	int i,j;
	int p,q;
	i=x;
	j=y;
	if(i==n&&j==0) 
    {
    	if(sum>max)
    	{
    		max=sum;
		}
    /*	printf("%d\n",sum);
    	printf("\n");
    	for(p=0;p<=n-1;p++)
    	{
    		for(q=0;q<=n-1;q++)
    		{
    			printf("%2d",bol[p][q]);
			}
			printf("\n");
		}*/
	}
	else
	{
		if(ke(i,j)&&bol[i][j]!=-1)
	    {
	    	if(j!=n-1)
	    	{
		    	bol[i][j]=1;//在此地放置
		    //	printf("测试%d %d\n",i,j);
				search(i,1+j,sum+1);
				bol[i][j]=0;//不在此地放置并重置
				search(i,j+1,sum);
			}
			else
			{
			    bol[i][j]=1;
			//   printf("测试%d %d\n",i,j);
				search(i+1,0,sum+1);
				bol[i][j]=0;
				search(i+1,0,sum);
			}
		}
		else
		{
			if(j!=n-1)
	    	{
	    		search(i,j+1,sum);
			}
			else
			{
				search(i+1,0,sum);
			}
		}
	}
   
}
int ke(int x,int y)
{
	int i,j;
	for(i=y+1;i<=n-1&&bol[x][i]!=-1;i++)//右侧敌人 
	{
		if(bol[x][i]==1)
		{
			return 0;
		}
	}
	for(i=y-1;i>=0&&bol[x][i]!=-1;i--)//左侧敌人 
	{
		if(bol[x][i]==1)
		{
			return 0;
		}
	}
	for(j=x+1;j<=n-1&&bol[j][y]!=-1;j++)//下侧敌人 
	{
		if(bol[j][y]==1)
		{
			return 0;
		}
	}
	for(j=x-1;j>=0&&bol[j][y]!=-1;j--)//上侧敌人
	{
		if(bol[j][y]==1)
		{
			return 0;
		}
	}
	return 1;
}

注释掉的是调试数据的输出。
可以把放置情况输出。