A39796. 移动路线
填空题
困难
知识点
题目描述
移动路线
题目描述
桌子上有一个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//蚂蚁共有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;
}
上一题
下一题