AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3398. 园区参观路径

中等通过率 47% · 提交 934 · 通过 436
动态规划矩阵DP

小慕的公司组织了一次Family Day活动,邀请员工和家属参观。园区被看作一个矩形网格,起点设在左上角,终点设在右下角。参观时,大家只能向右或向下移动。小慕想知道,从起点到终点一共有多少条

提示:带虚线的词点一下有通俗解释。

输入描述

<div data-page-id="FwYYdtTOno83Y9xbYXOcU76Zn8f" data-docx-has-block-data="false"> <div class="ace-line ace-line old-record-id-J5BKdiK86oFaBcx8VHVcB8d8nzg"> 第一行为园区长和宽;后面每一行表示该园区是否可以参观,<code>0</code>表示可以参观,<code>1</code>表示不能参观 </div> <div class="ace-line ace-line old-record-id-GOFwdJQyboYO7UxKqzQcJkHWnkd"> <code>1 <= 园区长, 园区宽 <= 100</code> </div> </div> <span data-lark-record-data="{"isCut":false,"rootId":"FwYYdtTOno83Y9xbYXOcU76Zn8f","parentId":"FwYYdtTOno83Y9xbYXOcU76Zn8f","blockIds":[8,9],"recordIds":["J5BKdiK86oFaBcx8VHVcB8d8nzg","GOFwdJQyboYO7UxKqzQcJkHWnkd"],"recordMap":{"J5BKdiK86oFaBcx8VHVcB8d8nzg":{"id":"J5BKdiK86oFaBcx8VHVcB8d8nzg","snapshot":{"type":"text","parent_id":"FwYYdtTOno83Y9xbYXOcU76Zn8f","comments":[],"revisions":null,"locked":false,"hidden":false,"author":"7115054903550050305","children":[],"text":{"initialAttributedTexts":{"text":{"0":"第一行为园区长和宽;后面每一行表示该园区是否可以参观,0表示可以参观,1表示不能参观"},"attribs":{"0":"*0+r*0*1+1*0+7*0*1+1*0+6"}},"apool":{"numToAttrib":{"0":["author","7115054903550050305"],"1":["inlineCode","true"]},"nextNum":2}},"align":"","folded":false}},"GOFwdJQyboYO7UxKqzQcJkHWnkd":{"id":"GOFwdJQyboYO7UxKqzQcJkHWnkd","snapshot":{"type":"text","parent_id":"FwYYdtTOno83Y9xbYXOcU76Zn8f","comments":[],"revisions":null,"locked":false,"hidden":false,"author":"7115054903550050305","children":[],"text":{"initialAttributedTexts":{"text":{"0":"1 <= 园区长, 园区宽 <= 100"},"attribs":{"0":"*0*1+k"}},"apool":{"numToAttrib":{"0":["author","7115054903550050305"],"1":["inlineCode","true"]},"nextNum":2}},"align":"","folded":false}},"FwYYdtTOno83Y9xbYXOcU76Zn8f":{"id":"FwYYdtTOno83Y9xbYXOcU76Zn8f","snapshot":{"type":"page","parent_id":"","comments":[],"revisions":[],"locked":false,"hidden":false,"author":"7115054903550050305","children":["doxcn23zMNec2Q5KB23hMYvpeef","doxcnwFIxR56r7fPICJQ99sA4Uh","LL8Ud8tZ0oOYxaxIN3DcBbvInNh","YBQbdyUlKoAImnx9CExcydtfn8g","doxcnvbkGnCaLxYNG09VCKWydEf","doxcnKqFYxk8rQSS4elXFPGjGpO","J5BKdiK86oFaBcx8VHVcB8d8nzg","GOFwdJQyboYO7UxKqzQcJkHWnkd","doxcnJQhbLTMRPUwGOLCAAn8dmb","doxcnPiMcvBCqBPrgWPa3QIi1Tc","UvMKdQecMoRc8jxp5zycgDcZnmh","doxcnsc1R3ILh5r1I5pi01uSZ7g","doxcnyh1eg7Ei9u8SKt6uLOfq4f","doxcnkUrQk5UDlJl5dyvNaTIGFe","doxcnizhFatieQo6fyGj1SpWPff","doxcnwo3VuyHQK0H6VbsPi2zJlg","doxcnE8hmReKWSmlVfzOq529Rke","doxcnju7uhV7lx9PKIjnh1OAAwb","doxcnarMTf6ecH0Cquc5iKHFvGc","doxcnZ3zgoJ1zwn39Tn9YN7k8ph","Ox3Kd0wNcocDWzxayESc9I4vnJf","V2XIdTc9xofJpsxGFgbcCzhJn0b","X9a7dvYYiojPgsxsKhbc1mAdnCc","CYV8dHyndoiaqGxoMkoc9MTenzc","doxcnRgCeoUqKO52iH0XcGGXr6f","doxcnkXy8wo83yuXeTohmcDI7Af","doxcn1YLUKnTXhoOrglHeCzKIyb","doxcnPq03qyFyuZpn9dpRBBc9eb","doxcnzkJ3U1gj0pJwJQHS8gxcjg","doxcnnQNONqqMD70geMZEsX8Ynh","doxcn637edQnYr7FKMZg4Ai64me","doxcnmvxfkJwftd1qlm9cZ9VLDb","doxcnmxGHONBBDkdqqXzFNuZnDh","doxcnBjVEHt8zWPDTvHPCWlTIah","doxcnPBdfakCWyPeRI3NYb2yETh","doxcnGhDWwIU7xJ1vFkkpzy5G4d","doxcndpQTG95jZdnR5No5s1nkEr","doxcnL8ebsThF313gyN6A1Fzofd"],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","7115054903550050305"]}},"initialAttributedTexts":{"attribs":{"0":"*0+g"},"text":{"0":"【DP】2023C-园区参观路径"}}},"align":"","doc_info":{"editors":["7115054903550050305"],"options":["editors","create_time"],"deleted_editors":[]}}}},"payloadMap":{"J5BKdiK86oFaBcx8VHVcB8d8nzg":{"level":1},"GOFwdJQyboYO7UxKqzQcJkHWnkd":{"level":1}},"extra":{"channel":"saas","mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"selection":[{"id":8,"type":"text","selection":{"start":0,"end":42},"recordId":"J5BKdiK86oFaBcx8VHVcB8d8nzg"},{"id":9,"type":"text","selection":{"start":0,"end":20},"recordId":"GOFwdJQyboYO7UxKqzQcJkHWnkd"}],"pasteFlag":"06500280-7465-4ea8-b6e3-348c26b1b2fd"}" data-lark-record-format="docx/record" class="lark-record-clipboard"></span>

输出描述

<div data-page-id="FwYYdtTOno83Y9xbYXOcU76Zn8f" data-docx-has-block-data="false"> <div class="ace-line ace-line old-record-id-UvMKdQecMoRc8jxp5zycgDcZnmh"> 输出为不同的路径数量 </div> </div>

示例

示例 1

输入

3 3
0 0 0
0 1 0
0 0 0

输出

2

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
0 0 0 0 1 0 0 0 0 起点 终点 路径1 路径2 3×3网格,中间格子为障碍(1) 只能向右或向下移动 共有2条不同路径
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「园区参观路径」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。