网站 › 『编程语言讨论求助区』 › 一道Java算法题

Axbro 发表于 2021-10-28 19:23

一道Java算法题

已知地图如下所示，小明家在坐标原点(0,0)，学校坐标（x，y），已知某2个点（可能为家或学校）在修路，因而不能通过这两点，小明走路只能向上和向右走，求出从家到达学校共有几种走法。下图中，修路的两点以黑点标识。
输入格式:首先输入测试组数T，然后输入T组测试；对于每组测试，输入学校坐标(x,y)，两个修路点坐标(x1, y1),(x2, y2)。其中，0<=x, y, x1, y1, x2, y2<=30。输出格式:对于每组测试，输出从家（0，0）到达学校（x,y）共有几种走法。输入样例:

kesai 发表于 2021-10-28 22:46

本帖最后由 kesai 于 2021-10-29 09:57 编辑

BFS应该可以吧，很久不写算法，忘记了，可能还是dfs更靠谱:keai

lostmilkyway 发表于 2021-10-28 23:16

对从坐标0,0到学校坐标x,y进行深度优先遍历，让变量res+1，对修路地点进行剪枝直接return就行

平淡最真 发表于 2021-10-29 00:43

C(14,6)-C(6,2)*C(8,4)-C(10,4)*C(4,2)+C(6,2)*C(4,2)*C(4,2)=1233
数学方法计算不知道算的对不对，谁写出来后帮我验证下

lyliucn 发表于 2021-10-29 08:33

Java不熟悉，好好学习。

nwl909690050 发表于 2021-10-29 09:04

完了，我身为JAVA程序员，无从下手

CCTV5 发表于 2021-10-29 09:37

请公布代码

asd_asd 发表于 2021-10-29 09:46

nwl909690050 发表于 2021-10-29 09:04
完了，我身为JAVA程序员，无从下手

算法题一般和编程语言没啥太大关系，主要看思路

jetranger 发表于 2021-10-29 10:00

算法说到底是数学题，算法要学好，首先还是要数学好。

VioletKiss 发表于 2021-10-29 11:17

用数学公式是最快的

查看完整版本: 一道Java算法题