主题：第76次编程比赛题目
mht@ [专家分：1260] 发布于 2008-11-03 18:33:00
一、过河问题
问题描述：
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入：
第一行有一个正整数L（1 <= L <=10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出：
只包括一个整数，表示青蛙过河最少需要踩到的石子数。
样例输入：
10
2 3 5
2 3 5 6 7
样例输出：
2
二、南极冰山问题
传说中，南极有一片广阔的冰原，在冰原下藏有史前文明的遗址。整个冰原被横竖划分成了很多个大小相等的方格。在这个冰原上有N个大小不等的矩形冰山，这些巨大的冰山有着和南极一样古老的历史，每个矩形冰山至少占据一个方格，且其必定完整地占据方格。冰山和冰山之间不会重叠，也不会有边或点相连。
ACM探险队在经过多年准备之后决定在这个冰原上寻找遗址。根据他们掌握的资料，在这个冰原上一个大小为一格的深洞中，藏有一个由史前人类制作的开关。而唯一可以打开这个开关的是一个占据接近一格的可移动的小冰块。显然，在南极是不可能有这样小的独立冰块的，所以这块冰块也一定是史前文明的产物。他们在想办法把这个冰块推到洞里去，这样就可以打开一条通往冰原底部的通道，发掘史前文明的秘密。冰块的起始位置与深洞的位置均不和任何冰山相邻。
这个冰原上的冰面和冰山都是完全光滑的，轻轻的推动冰块就可以使这个冰块向前滑行，直到撞到一座冰山就在它的边上停下来。冰块可以穿过冰面上所有没有冰山的区域，也可以从两座冰山之间穿过。冰块只能沿网格方向推动。
输入
输入文件第一行为冰山的个数N (1<=N<=4000)，第二行为冰块开始所在的方格坐标X1,Y1，第三行为深洞所在的方格坐标X2,Y2，以下N行每行有四个数，分别是每个冰山所占的格子左上角和右下角坐标Xi1,Yi1,Xi2,Yi2 （坐标都在int 型范围内即 -2^31到2^31)
输出
输出文件仅包含一个整数，为最少推动冰块的次数。如果无法将冰块推入深洞中，则输出0。
样例输入
2
1 1
5 5
1 3 3 3
6 2 8 4
样例输出
3
时间：截止到本周日中午
最后更新于：2008-11-05 14:21:00
回复列表 （共19个回复）
12 楼
iori2oo2 [专家分：0] 发布于 2008-11-09 01:12:00
henhao
13 楼
yj1221 [专家分：20] 发布于 2008-11-09 11:41:00
//----in.txt
10
2 3 5
2 3 5 6 7
//---------------
// 穷举法 求解 ---
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
bool findStonePos(int keyWord, int *pos, int n); // 返回从 pos[] 中开始找 keyWord , 找到返回 true , 否则 返回 false
bool produceArray(int *result, int n, int min, int max);
int findSumStonePos(int *stepInfo, int m, int *stonePos, int n); // 返回从 pos[] 中开始找 stepInfo[], 走, 所有踏上石头的数目
int main()
{
ifstream in("c:\\in.txt");
int length;
in >> length;
int minSpead, maxSpead;
in >> minSpead;
in >> maxSpead;
int sumStones;
in >> sumStones;
int *stonePos = new int [sumStones];
for(int i = 0; i < sumStones; ++i)
in >> stonePos[i];
// 求出最大的步数
int maxSteps;
if(length % minSpead == 0)
maxSteps = length / minSpead;
else
maxSteps = length / minSpead+ 1;
int *stepInfo = new int[maxSteps]; // 存储每次 跳的步数
for(i = 0; i < maxSteps; ++i)
stepInfo[i] = minSpead;
int minStoneSteps = maxSteps; // 最少踏在石头上的步数
int iSumStones = 0; // 本次踏上石头的数目
while( produceArray(stepInfo, maxSteps, minSpead, maxSpead) )
{
iSumStones = findSumStonePos(stepInfo, maxSteps, stonePos, sumStones);
if( iSumStones < minStoneSteps)
minStoneSteps = iSumStones;
}
cout << minStoneSteps << endl;
delete stonePos;
delete stepInfo;
in.close();
return 0;
}
bool findStonePos(int keyWord, int *pos, int n)
{ // 返回从 pos[] 中开始找 keyWord , 找到返回 true , 否则 返回 false
for(int i = 0; i < n; ++i)
{
if(pos[i] == keyWord)
return true;
}
return false;
}
int findSumStonePos(int *stepInfo, int m, int *stonePos, int n)
{ // 返回从 pos[] 中开始找 stepInfo[], 走, 所有踏上石头的数目
int pos = 0;
int sum = 0;
for(int i = 0; i < m; ++i)
{
pos += stepInfo[i];
if( findStonePos(pos, stonePos, n) )
sum++;
}
return sum;
}
bool produceArray(int *result, int n, int min, int max)
{ // 产生 {min, min, ... ,min} 到 {max, max, ... , max} 的数, 增数为 1
// 当产生 {max+1, 0, ... , 0} 返回false
result[0] ++ ;
int i = 0;
while(result[i] > max && i < n-1)
{
result[i] = min;
i++;
result[i] ++;
}
if(result[n-1] > max)
return false;
else
return true;
}
14 楼
yj1221 [专家分：20] 发布于 2008-11-09 11:43:00
// ------in.txt
10
2 3 5
2 3 5 6 7
// -----------------
// 穷尽法求解
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
bool findStonePos(int keyWord, int *pos, int n); // 返回从 pos[] 中开始找 keyWord , 找到返回 true , 否则 返回 false
bool produceArray(int *result, int n, int min, int max);
int findSumStonePos(int *stepInfo, int m, int *stonePos, int n); // 返回从 pos[] 中开始找 stepInfo[], 走, 所有踏上石头的数目
int main()
{
ifstream in("c:\\in.txt");
int length;
in >> length;
int minSpead, maxSpead;
in >> minSpead;
in >> maxSpead;
int sumStones;
in >> sumStones;
int *stonePos = new int [sumStones];
for(int i = 0; i < sumStones; ++i)
in >> stonePos[i];
// 求出最大的步数
int maxSteps;
if(length % minSpead == 0)
maxSteps = length / minSpead;
else
maxSteps = length / minSpead+ 1;
int *stepInfo = new int[maxSteps]; // 存储每次 跳的步数
for(i = 0; i < maxSteps; ++i)
stepInfo[i] = minSpead;
int minStoneSteps = maxSteps; // 最少踏在石头上的步数
int iSumStones = 0; // 本次踏上石头的数目
while( produceArray(stepInfo, maxSteps, minSpead, maxSpead) )
{
iSumStones = findSumStonePos(stepInfo, maxSteps, stonePos, sumStones);
if( iSumStones < minStoneSteps)
minStoneSteps = iSumStones;
}
cout << minStoneSteps << endl;
delete stonePos;
delete stepInfo;
in.close();
return 0;
}
bool findStonePos(int keyWord, int *pos, int n)
{ // 返回从 pos[] 中开始找 keyWord , 找到返回 true , 否则 返回 false
for(int i = 0; i < n; ++i)
{
if(pos[i] == keyWord)
return true;
}
return false;
}
int findSumStonePos(int *stepInfo, int m, int *stonePos, int n)
{ // 返回从 pos[] 中开始找 stepInfo[], 走, 所有踏上石头的数目
int pos = 0;
int sum = 0;
for(int i = 0; i < m; ++i)
{
pos += stepInfo[i];
if( findStonePos(pos, stonePos, n) )
sum++;
}
return sum;
}
bool produceArray(int *result, int n, int min, int max)
{ // 产生 {min, min, ... ,min} 到 {max, max, ... , max} 的数, 增数为 1
// 当产生 {max+1, 0, ... , 0} 返回false
result[0] ++ ;
int i = 0;
while(result[i] > max && i < n-1)
{
result[i] = min;
i++;
result[i] ++;
}
if(result[n-1] > max)
return false;
else
return true;
}
15 楼
yj1221 [专家分：20] 发布于 2008-11-09 11:46:00
// c\\mapIn.txt
2
1 1
5 5
1 3 3 3
6 2 8 4
//--------------------
// 时间来不及了，程序老是死循环，先提交，也算参加了比赛。
#include <iostream>
#include <stack>
#include <fstream>
#include <stdlib.h>
using namespace std;
#define N 10
struct posType{
int x;
int y;
};
struct mapPosType{
posType seat;
// 规定 0 向右方走， 顺时针依次增加，最大方向为 3
// int enterDi; // 开始进入堆栈的方向
int nextDi; // 下一个方向
};
stack<mapPosType> mapElemStack; // 存储走的路线
int mapInfo[N][N]; // 开始初始化地图信息
bool getNextPos(mapPosType & pos); // 得到当前位置pos 的下一个位置，若不能得到，返回false
bool isEqual(posType &a, posType &b); // 判断位置a 和 位置 b 是否相等
int main(void)
{
ifstream in("c:\\mapIn.txt");
int sumM; // 总共的冰山数目
in >> sumM;
mapPosType start, end;
in >> start.seat.x;
in >> start.seat.y;
// start.enterDi = 0;
start.nextDi = 0;
in >> end.seat.x;
in >> end.seat.y;
int rowStart, rowEnd, columStart, columEnd;
for(int i = 0; i < sumM; ++i)
{
in >> rowStart;
in >> columStart;
in >> rowEnd;
in >> columEnd;
for(int r = rowStart; r <= rowEnd; ++r)
{
for(int c = columStart; c <= columEnd; ++c)
mapInfo[r][c] = 1;
}
}
mapElemStack.push(start);
int minSumCount = 0xffffff;
int count = 0;
while( !mapElemStack.empty() )
{
mapPosType temp;
temp = mapElemStack.top();
if( getNextPos(temp) ) // 得到下一个位置，若得不到，返回false
{
if( isEqual(temp.seat, end.seat) )
{
if(count < minSumCount)
{
minSumCount = count;
// 先不管最小的了，只输出一种结果
cout << minSumCount << endl;
return 0;
}
}
mapElemStack.push(temp);
// 转换了一次
count++;
cout << "(" << temp.seat.x << "," << temp.seat.y << ")" << endl;
// cout << count << endl;
}
else
{
while( !getNextPos(temp) )
{
mapElemStack.pop();
if(!mapElemStack.empty())
temp = mapElemStack.top();
else
break;
}
temp.nextDi++;
}
// temp.nextDi++;
}
in.close();
return 0;
}
16 楼
yj1221 [专家分：20] 发布于 2008-11-09 11:46:00
bool getNextPos(mapPosType & pos)
{ // 得到当前位置pos 的下一个位置，若不能得到，返回false
// int enterDi = pos.enterDi;
if( pos.nextDi == 4 )
{
return false;
}
int i;
switch( pos.nextDi )
{
case 0:
for(i = pos.seat.y; i < N && mapInfo[pos.seat.x][i] != 1; i++);
if(i == N || mapInfo[pos.seat.x][pos.seat.y+1] == 1 )
return false;
else
{
pos.seat.y = i-1;
return true;
}
break;
case 1:
for(i = pos.seat.x; i < N && mapInfo[i][pos.seat.y] != 1; ++i);
if(i == N || mapInfo[pos.seat.x+1][pos.seat.y] == 1)
return false;
else
{
pos.seat.x = i-1;
return true;
}
break;
case 2:
for(i = pos.seat.y; i > 0 && mapInfo[pos.seat.x][i] != 1; --i);
if(i == 0 || mapInfo[pos.seat.x][pos.seat.y-1] == 1)
return false;
else
{
pos.seat.y = i+1;
return true;
}
break;
case 3:
for(i = pos.seat.x; i > 0 && mapInfo[i][pos.seat.y] != 1; --i);
if(i == 0 || mapInfo[pos.seat.x-1][pos.seat.y] == 1)
return false;
else
{
pos.seat.x = i+1;
return true;
}
break;
default:
cout << "方向错误！ " << endl;
exit(0);
}
}
bool isEqual(posType &a, posType &b)
{ // 判断位置a 和 位置 b 是否相等
if( a.x == b.x && a.y == b.y)
return true;
else
return false;
}
17 楼
mht@ [专家分：1260] 发布于 2008-11-09 11:52:00
在网上找了半天也没找到测试数据！！不好意思啊.
只能自己做几个，谁要是有，帮忙贴上来啊
第一题，网上的题解比较多，主要是dp状态压缩！
第二题，是BFS，我开始想用双向广度搜索算法，到最后才发现不行，一开始没想清楚，还是单向好！
这是我第二题的程序：
#include <iostream>
using namespace std;
#define Max 16000
int N;
struct tnode
{
int x,y;
int flag; // 推动计数
tnode(){flag=0;}
}star[Max],end;
struct Snode
{
int x1,y1,x2,y2;
}Stone[4001];
// 初始化队列，输入初始点，目标点和冰山位置——————————————————
void init()
{
cout<<"输入冰山的个数N (1<=N<=4000)："<<endl;
cin>>N;
cout<<"输入初始位置的坐标："<<endl;
cin>>star[0].x>>star[0].y;
cout<<"输入目标位置的坐标;"<<endl;
cin>>end.x>>end.y;
for(int i=0;i<N;i++)
cin>>Stone[i].x1>>Stone[i].y1>>Stone[i].x2>>Stone[i].y2;
Stone[N].x1=Stone[N].x2=end.x;
Stone[N].y1=Stone[N].y2=end.y;
}
18 楼
mht@ [专家分：1260] 发布于 2008-11-09 11:54:00
// 检测能否扩展，能则产生新节点————————————————————————
bool expand(tnode &temp,int F)
{
struct tnode Stemp;
Stemp=temp;
int k;
if(F==0)
{
k=0x7fffffff;
for(int j=0;j<N+1;j++)
{
if(temp.y>=Stone[j].y1&&temp.y<=Stone[j].y2)
if(Stone[j].x1>temp.x)
k=k<Stone[j].x1?k:Stone[j].x1;
}
if(k!=0x7fffffff)
{
if(k==end.x&&temp.y==end.y)
Stemp.x=k;
else
Stemp.x=k-1;
}
if(Stemp.x!=temp.x)
{
temp=Stemp;
temp.flag=temp.flag+1;
return 1;
}
else return 0;
}
else if(F==1)
{
k=0x7fffffff;
for(int j=0;j<N+1;j++)
{
if(temp.x>=Stone[j].x1&&temp.x<=Stone[j].x2)
if(Stone[j].y1>temp.y)
k=k<Stone[j].y1?k:Stone[j].y1;
}
if(k!=0x7fffffff)
{
if(k==end.y&&temp.x==end.x)
Stemp.y=k;
else
Stemp.y=k-1;
}
if(Stemp.y!=temp.y)
{
temp=Stemp;
temp.flag=temp.flag+1;
return 1;
}
else return 0;
}
else if(F==2)
{
k=-0x7fffffff;
for(int j=0;j<N+1;j++)
{
if(temp.y>=Stone[j].y1&&temp.y<=Stone[j].y2)
if(Stone[j].x2<temp.x)
k=k<Stone[j].x2?Stone[j].x2:k;
}
if(k!=-0x7fffffff)
{
if(k==end.x&&temp.y==end.y)
Stemp.x=k;
else
Stemp.x=k+1;
}
if(Stemp.x!=temp.x)
{
temp=Stemp;
temp.flag=temp.flag+1;
return 1;
}
else return 0;
}
else if(F==3)
{
k=-0x7fffffff;
for(int j=0;j<N+1;j++)
{
if(temp.x>=Stone[j].x1&&temp.x<=Stone[j].x2)
if(Stone[j].y2<temp.y)
k=k<Stone[j].y2?Stone[j].y2:k;
}
if(k!=-0x7fffffff)
{
if(k==end.y&&temp.x==end.x)
Stemp.y=k;
else
Stemp.y=k+1;
}
if(Stemp.y!=temp.y)
{
temp=Stemp;
temp.flag=temp.flag+1;
return 1;
}
else return 0;
}
return 0;
}
19 楼
mht@ [专家分：1260] 发布于 2008-11-09 11:55:00
// 判断是否有重复的节点——————————————————————————————
bool repeat(tnode state[],tnode temp,int tail)
{
for(int i=0;i<=tail;i++)
if(state[i].x==temp.x&&state[i].y==temp.y)
return 1;
return 0;
}
// 是否为目标————————————————————————————————
bool find(tnode temp,tnode end)
{
if(temp.x==end.x&&temp.y==end.y)
return 1;
else
return 0;
}
// 广度搜索函数————————————————————————————————
void bfs()
{
tnode temp;
int head=0,tail=0;
while(head<=tail&&tail<Max)
{
for(int i=0;i<4;i++)
{
temp=star[head];
if(expand(temp,i))
{
if(repeat(star,temp,tail))
continue;
star[++tail]=temp;
if(find(temp,end))
{
cout<<temp.flag<<endl; //????
exit(0);
}
}
}
head++;
}
cout<<"Error!!!"<<endl;
}
int main()
{
init();
bfs();
return 0;
}
我来回复
您所在位置：