Algorithm|ZOJ练习--002Fire Net python|算法|exercise

题目描述 【Algorithm|ZOJ练习--002Fire Net】Fire Net: 题目大意为在一个二维的网格平面中（城市），实心方块是障碍物（或称为不可摧毁建筑），实心是炮台，空白方块是空地（或者称为可摧毁建筑）。炮弹可以在没有障碍物的情况下，可以打得足够远，问在给定的一个平面网格中，至少可以放置多少个炮台，就可以覆盖整个二维网格平面的空地（城市）。
数据描述：城市用一个 n × n n \times n n×n 2D数组表示，其中‘.’表示空地，‘x’代表障碍物,n表示城市大小。
题目详细描述请参考ZOJ002
解题思路一：使用递归试探的方式，也就是每一空地，都可以原则架设炮台，或者继续空着。然后对新的城市进行检验，看是否符合要求。若不符合要求，则不能架设炮台，然后进入下一个位置。若符合要求，则炮台数量+1直到便利完所有的空地，并记录最大的炮台数。最后统计出来的最大炮台数，就是我们要求的结果。
代码如下：

import sysdef input_city(n): ''' :param n: city 规模 :return: 输入的city ''' city = [] for i in range(n): city.append(list(sys.stdin.readline().upper())) return citydef check(city, pos): ''' :param city: city地图 :param pos: 需要check的位置 :return: 返回该位置能否放置炮台 ''' pos_x = int(pos / len(city)) pos_y = int(pos % len(city)) if city[pos_x][pos_y] == '.': i, j = pos_x, pos_y while j > 0: j -= 1 if city[pos_x][j] == 'F': return False if city[pos_x][j] == 'X': break; while i > 0: i -= 1 if city[i][pos_y] == 'F': return False if city[i][pos_y] == 'X': break; i, j = pos_x, pos_y while j < len(city) - 1: j += 1 if city[pos_x][j] == 'F': return False if city[pos_x][j] == 'X': break; while i < len(city) - 1: i += 1 if city[i][pos_y] == 'F': return False if city[i][pos_y] == 'X': break; return True elif city[pos_x][pos_y] == 'X': return Falsedef counter(city): ''' :param city: 带炮台的city :return: city的炮台数 num ''' num = 0 for c in city: for i in c: if i == ('F' or 'f'): num += 1 return nummax = 0def max_num(city, pos): ''' :param city: :param pos: :return: city最大炮台数 ''' global max if pos == (len(city)) ** 2: count = counter(city) if count > max: max = count else: if check(city, pos): pos_x = int(pos / len(city)) pos_y = int(pos % len(city)) city[pos_x][pos_y] = 'F' max_num(city, pos + 1) city[pos_x][pos_y] = '.' max_num(city, pos + 1) else: max_num(city, pos + 1) return maxif __name__ == '__main__': citys = [] while True: n = int(input()) if n == 0: break else: citys.append(input_city(n)) for city in citys: print(max_num(city, 0)) max = 0

联系邮箱:antarm@outlook.com