青少年软件编程（C语言） 等级考试试卷（四级）12月
1.移动路线
题目描述
桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。
小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。
对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……对于一个2行3列的方格矩阵，如下图所示：
蚂蚁一共有3种移动路线：
路线1：(1,1) - (1,2) - (1,3) - (2,3)
路线2：(1,1) - (1,2) - (2,2) - (2,3)
路线3：(1,1) - (2,1) - (2,2) - (2,3)
输入描述
输入只有一行，包括两个整数m和n（0 < m+n ≤ 20），代表方格矩阵的行数和列数，m、n之间用空格隔开。
输出描述
输出若干行，每行一个移动路线，输出形式如样例所示。
（为保证输出一致，蚂蚁移动时先向右，再向上）
输入
2 3
输出
蚂蚁共有3种移动路线：
路线1：(1,1) - (1,2) - (1,3) - (2,3)
路线2：(1,1) - (1,2) - (2,2) - (2,3)
路线3：(1,1) - (2,1) - (2,2) - (2,3)
————————————————
#include<iostream>
#include<cstdio>
using namespace std;
const int N=40;
const int dx[2]={0,1};
const int dy[2]={1,0};
int n,m,ans=0;
bool flag=false;
struct node{
int x;
int y;
}st[N*N],tu[N*N][N*N];
int a[N*N];
bool ran_out(int x,int y){
return x<1||x>n||y<1||y>m;
}
void fuzhi(int step){
ans++;
a[ans]=step;
flag=true;
for(int i=0;i<=step;i++){
tu[ans][i].x=st[i].x;
tu[ans][i].y=st[i].y;
}
}
void dfs(int x,int y,int step){
st[step].x=x;
st[step].y=y;
if(x==n&&y==m){
fuzhi(step);
return;
}
for(int i=0;i<2;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(!ran_out(xx,yy)){
dfs(xx,yy,step+1);
}
}
}
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>m;
dfs(1,1,0);
printf("蚂蚁共有%d种移动路线：\n",ans);
for(int i=1;i<=ans;i++){
printf("路线%d：",i);
bool ff=false;
for(int j=0;j<=a[i];j++){
if(!ff){
printf("(%d,%d)",tu[i][j].x,tu[i][j].y);
ff=true;
}else{
printf(" - (%d,%d)",tu[i][j].x,tu[i][j].y);
}
}
printf("\n");
}
return 0;
}
2.移动办公
题目描述
假设你经营着一家公司，公司在北京和南京各有一个办公地点。公司只有你一个人，所以你只能每月选择在一个城市办公。在第i个月，如果你在北京办公，你能获得Pi的营业额，如果你在南京办公，你能获得Ni的营业额。但是，如果你某个月在一个城市办公，下个月在另一个城市办公，你需要支付M的交通费。那么，该怎样规划你的行程（可在任何一个城市开始），才能使得总收入（总营业额减去总交通费）最大？
输入
输入的第一行有两个整数T（1 <= T <= 100）和M（1 <= M <= 100），T代表总共的月数，M代表交通费。接下来的T行每行包括两个在1到100之间（包括1和100）的的整数，分别表示某个月在北京和在南京办公获得的营业额。
输出
输出只包括一行，这一行只包含一个整数，表示可以获得的最大总收入。
样例输入
4 3
10 9
2 8
9 5
8 2
1
2
3
4
5
样例输出
31
更多内容请查看网站：
网站链接
青少年软件编程历年真题模拟题实时更新
