求编程大赛冠军
这是一个只有一个棋子的游戏。棋盘分为n行m列，某个位置标记为终点t，在任意位置，棋子可以左右上下移动一格，移动距离为1。
棋盘上有一些特殊的方格——飞机。每架飞机都有一个飞行距离D，棋子到达后可以继续同方向“飞”D方块，移动距离仍为1。比如棋子在(2，8)位置，飞机在(2，7)位置，飞行距离为5，那么棋子会直接走到(2，2)位置，移动距离为1。如果飞点落在棋盘外，只能停在边界。比如前一架飞机的飞行距离是10，那么棋子的最终位置就是(21)。
而且如果飞行后的落点仍然是飞行器，那么它会继续飞向目的地，中间点不会影响当前棋子，当然也不会算作任何移动距离。比如棋子在(2，8)，飞机在(2，7)和(2，5)，飞行距离是5，那么棋子向左移动一格，那么(2，5)的飞机就不起作用，移动距离还是1。
你的任务是编程并计算棋子到达终点的最短移动距离。
输入:
输入可以有多个测试用例。每个测试用例的第一行是两个整数n，m (3
输出:
每个测试用例输出一行，即到终点的最短距离。如果无法实现，则输出“不可能”。
二、最小硬币数:
这个问题输入起来感觉特别麻烦，希望能给出更好的输入法。
这是一个古老而经典的问题。一般来说，有很多方法可以用给定数量的硬币赚到一定数量的钱。例如，给定面额为2、5、10、20、50、100的六种硬币，要凑成1 5元，可以用五个2元，1 5元，或者三个5元，或者15元，15元。显然，至少需要2个硬币才能凑足15元。
你的任务是给出一些不同面值的硬币，编程并计算出至少需要多少硬币才能组成给定的金额。
输入:
输入可以有多个测试用例。每个测试用例的第一行是货币值m (1
输出:
每个测试用例输出一行，即组成货币值m所需的最小硬币数，如果收集失败，输出“不可能”。你可以假设要收集的每个硬币的数量是无限的。
样本输入:
15
6 2 5 10 20 50 100
1
1 2
样本输出:
2
不可能第一个问题的最佳答案是，典型的BFS会找到最短的路径。
# include & ltiostream & gt
#定义MAXN 105
使用命名空间std
const int dir[4][2]={{0，1}，{0，-1}，{1，0}，{-1，0 } }；
int m，n；
int map[MAXN][MAXN]；
int head，tail
int queue[MAXN * MAXN][3]；
布尔哈希[MAXN][MAXN]；
int tx，ty；
int main()
{
而(CIN & gt；& gtn & gt& gtm & amp& ampn & gt0)
{
int i，j，k；
memset(map，0，sizeof(map))；
CIN & gt；& gtk；
while (k -)
{
CIN & gt；& gt我& gt& gtj；
I-；
j-；
CIN & gt；& gtmap[I][j]；
}
memset(hash，true，sizeof(hash))；
CIN & gt；& gt队列[0][0]& gt；& gt队列[0][1]；
队列[0][0]-；
队列[0][1]-；
队列[0][2]= 0；
hash[queue[0][0]][queue[0][1]]= false；
head = 0；
tail = 1；
CIN & gt；& gttx & gt& gtty；
tx-；
ty-；
while(head & lt；尾巴& amp& amp哈希[tx][ty])
{
for(k = 0；k & lt4;k++)
{
I =队列[头][0]+目录[k][0]；
j =队列[head][1]+dir[k][1]；
while(I & gt；= 0 & amp& amp我& ltn & amp& ampj & gt= 0 & amp& ampj & ltm & amp& ampmap[I][j]& gt；0)
{
I+= map[I][j]* dir[k][0]；
j+= map[I][j]* dir[k][1]；
如果(我& lt0 | | i & gt= n | | j & lt0 | | j & gt=m)
{
如果(我& lt0)I = 0；
如果(i & gt= n)I = n-1；
if(j & lt；0)j = 0；
if(j & gt；= m)j = m-1；
打破；
}
}
如果(i & gt= 0 & amp& amp我& ltn & amp& ampj & gt= 0 & amp& ampj & ltm)
if(哈希[i][j])
{
queue[tail][0]= I；
queue[tail][1]= j；
queue[tail][2]= queue[head][2]+1；
hash[I][j]= false；
if(I = = tx & amp；& ampj = = ty)cout & lt；& ltqueue[tail][2]& lt；& ltendl
tail++；
}
}
head++；
}
if(hash[tx][ty])cout & lt；& lt“不可能”& lt& ltendl
}
返回0；
}
第二个问题是典型的DP。
F[i][j]表示用前I种货币的总数J来凑整货币所需的最少硬币数。
状态转移方程f[I][j]= min { f[I-1][j](I >；0)，f[I][j-Ki]+1(j & gt；=Ki)，infinity }；
# include & ltiostream & gt
#定义MAXM 2010
# define me MAXK 15
使用命名空间std
int m，k；
int K[MAXK]；
int f[MAXK][MAXM]；
int main()
{
而(CIN & gt；& gtm & amp& ampm & gt0)
{
int i，j；
CIN & gt；& gtk；
for(I = 1；我& lt= k；i++)CIN & gt；& gtk[I]；
memset(f，-1，sizeof(f))；
f[0][0]= 0；
for(I = 1；我& lt= k；i++)
for(j = 0；j & lt= m；j++)
{
int min
min =-1；
if (f[i-1][j]！=-1 & amp；& amp(min = =-1 | | f[I-1][j]& lt；min))min = f[I-1][j]；
if(j & gt；= K[I]& amp；& ampf[i][j-K[i]]！=-1 & amp；& amp(min = =-1 | | f[I][j-K[I]]+1 & lt；min))min = f[I][j-K[I]]+1；
f[I][j]= min；
}
if(f[k][m]= =-1)cout & lt；& lt“不可能”& lt& ltendl
else cout & lt& ltf[k][m]& lt；& ltendl
}
返回0；
}