猫史档案馆

 

我遇到一道题，是这样的

题目背景

最近小明迷上了个游戏，玩家有一个基地以及N个导弹。导弹有不同的型号，射程和威力也不一样。小明想编一个程序来帮助他计算如何节省导弹。

题目描述

#是基地，*是攻击目标，0是空地。每个导弹都有射程（发射最远距离）和伤害范围（以导弹为中心，奇数边长的正方形）。请你计算最少需要多少导弹才能摧毁所有目标。如果无法达到目标，则输出“impossible”

输入格式

第一行两个数N和M，分别是地图的长和宽。

接着N行，每行M个字符，0表示空地，*表示目标，#表示基地

第N+2行为导弹个数K

接下来K行，每行两个数，分别是射程L，以及范围正方形的边长X

输出格式

一个数，表示最少需要几个导弹才能摧毁所有目标。如过果达不到，则输出“impossible”

说明/提示

基地只有一个

目标数<N*M-3

M，N≤500

K≤2500

L≤N+M，

X<500

注意！千万不能把基地也炸毁了！

然后……就没有然后了