UC知道程序设计大赛试题
来源：百度知道 编辑：UC知道 时间：2024/06/02 12:15:02
下面是两道程序设计大赛试题,望哪位高人可以解出来(用C或C++，平台是VC6.0)
一、行棋游戏:
这是一种只有一个棋子的游戏。棋盘被分为N行,M列的方格,某个位置被标记为终点T。在任何一个位置，棋子可以向左、右、上、下四个方向移动一格，记移动距离为1。
在棋盘上有一些特殊方格——飞行器，每个飞行器有一个飞行距离d，棋子达到后可以继续在同方向再“飞”d格，且移动距离仍然为1。例如，如果棋子在位置（2，8），飞行器在位置（2，7），且飞行距离为5，那么棋子向左走一格，将直接到达位置（2，2）且移动距离为1。如果飞行点落在棋盘外，则只能停在边界上。例如，假若前个飞行器的飞行距离为10，那么棋子的最终位置是（2，1）。
而且，如果飞行后的落点仍然是飞行器，则将连续飞行到目的地，且中间点不对当前棋子产生影响，当然也不算任何移动距离。例如，如果棋子位置在（2，8），飞行器在（2，7）、（2，5），且飞行距离都是5，此时棋子向左移动一格，则（2，5）的飞行器将不产生作用，移动距离仍然为1。
你的任务就是，编程计算出棋子达到终点的最短移动距离。
输入：
输入可以有多个测试用例。每个测试用例的第一行是两个整数N、M（3<=N, M<=100)，表示棋盘的行列数。随后是一个整数K，表示飞行器的个数。接着的K行每行有3个正整数x、y、d，分别表示飞行器的位置（x,y)(2 <= x <= N-1, 2 <= y <= M-1)及飞行距离d。最后的两行第一行是棋子的初始位置S，第二行是终点位置T。你可以假设数据总是合法的，S与T、飞行器位置互不相同。输入0 0时表示结束
输出：
每个测试用例输出一行，即达到终点的最短距离。如果不能达到，则输出“Impossible”。
二、最少钱币数：
（这个问题的输入我感觉特别麻烦，希望给出比较好的输入方法）
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要
一、行棋游戏:
这是一种只有一个棋子的游戏。棋盘被分为N行,M列的方格,某个位置被标记为终点T。在任何一个位置，棋子可以向左、右、上、下四个方向移动一格，记移动距离为1。
在棋盘上有一些特殊方格——飞行器，每个飞行器有一个飞行距离d，棋子达到后可以继续在同方向再“飞”d格，且移动距离仍然为1。例如，如果棋子在位置（2，8），飞行器在位置（2，7），且飞行距离为5，那么棋子向左走一格，将直接到达位置（2，2）且移动距离为1。如果飞行点落在棋盘外，则只能停在边界上。例如，假若前个飞行器的飞行距离为10，那么棋子的最终位置是（2，1）。
而且，如果飞行后的落点仍然是飞行器，则将连续飞行到目的地，且中间点不对当前棋子产生影响，当然也不算任何移动距离。例如，如果棋子位置在（2，8），飞行器在（2，7）、（2，5），且飞行距离都是5，此时棋子向左移动一格，则（2，5）的飞行器将不产生作用，移动距离仍然为1。
你的任务就是，编程计算出棋子达到终点的最短移动距离。
输入：
输入可以有多个测试用例。每个测试用例的第一行是两个整数N、M（3<=N, M<=100)，表示棋盘的行列数。随后是一个整数K，表示飞行器的个数。接着的K行每行有3个正整数x、y、d，分别表示飞行器的位置（x,y)(2 <= x <= N-1, 2 <= y <= M-1)及飞行距离d。最后的两行第一行是棋子的初始位置S，第二行是终点位置T。你可以假设数据总是合法的，S与T、飞行器位置互不相同。输入0 0时表示结束
输出：
每个测试用例输出一行，即达到终点的最短距离。如果不能达到，则输出“Impossible”。
二、最少钱币数：
（这个问题的输入我感觉特别麻烦，希望给出比较好的输入方法）
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要
第一题，典型的BFS找最短路
#include <iostream>
#define MAXN 105
using namespace 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];
bool hash[MAXN][MAXN];
int tx,ty;
int main()
{
while (cin>>n>>m && n>0)
{
int i,j,k;
memset(map,0,sizeof(map));
cin>>k;
while (k--)
{
cin>>i>>j;
i--;
j--;
cin>>map[i][j];
}
memset(hash,true,sizeof(hash));
cin>>queue[0][0]>>queue[0][1];
queue[0][0]--;
queue[0][1]--;
queue[0][2]=0;
hash[queue[0][0]][queue[0][1]]=false;
head=0;
tail=1;
cin>>tx>>ty;
tx--;
ty--;
while (head<tail && hash[tx][ty])
{
for (k=0;k<4;k++)
{
i=queue[head][0]+dir[k][0];
j=queue[head][1]+dir[k][1];
while (i>=0 && i<n && j>=0