1570C 旅行

2024-08-28 17:48

文章标签 旅行 1570c

本文主要是介绍1570C 旅行，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

Tom和Alice结婚一段时间了，感情非常好，一天他们相约去旅行，终点在遥远的地方。

地形是非常复杂的，路途是非常曲折的。但我们简化一下是一个矩阵。起点也就是他们家在矩阵的左下角，终点也就是他们要去的遥远的地方在右上角，矩阵行列的交点是他们可以驻足的地方，但是有的却是陷阱，他们是不能从那里通过的。Tom要听Alice的，只会往上或往右走，不往回走，直到终点。

Alice要Tom提前算出从起点到终点一共有多少条路，可Tom不会啊，所以就找到你了，你是编程高手，希望你帮他解决这个问题，不然他们的婚姻就有危机了。

输入

输入数据的第一行是两个正整数 H ， W(2 < H ， W < 20), 代表矩阵的高和宽。接下来是一个矩阵，共 H 行，每行 W 个元素，用空格隔开，元素取值只有 0 或 1 ， 0 表示可以走， 1 表示是陷阱，数据保证位于起点和终点的元素肯定是 0 。

输出

输出一个整数，即从起点到终点的路径数。

示例输入

5 51 1 1 1 00 0 1 1 00 0 0 0 01 0 1 0 10 0 0 0 0

示例输出

提示

类比于马踏过河卒,开始看书上的马踏过河卒，我以为是吧数组a中的陷阱变成1存入b。

后来听同学说是一条一条的找路线。

#include <stdio.h>
int main()
{
int a[20][20], i, j, b[20][20], m, n;
scanf("%d%d", &m, &n);
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
scanf("%d", &a[i][j]);
}
for(i = m - 2; i >= 0; i--)
{
if(a[i][0] == 0) b[i][0] = 1;
else
{
for(; i >= 0; i--)
b[i][0] = 0; //确定边缘的路线

}
}
for(j = 1; j < n; j++)
{
if(a[m-1][j] == 0) b[m-1][j] = 1;
else
{
for(; j < n; j++)
b[m-1][j] = 0; //确定边缘的路线

}
}
for(i = m - 2; i >= 0; i--)
{
for(j = 1; j < n; j++)
{
if(a[i][j] == 1)
b[i][j] = 0;
else
b[i][j] = b[i+1][j] + b[i][j-1];
}
}
printf("%d\n", b[0][n-1]);
return 0;

}

这篇关于1570C 旅行的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！