当前位置：网站首页>[leetcode weekly race] game 300 - 6110 Number of incremental paths in the grid graph - difficult
[leetcode weekly race] game 300 - 6110 Number of incremental paths in the grid graph - difficult
2022-07-03 18:42:00 【51CTO】
6110. The number of incremental paths in the grid graph
Difficulty 6 Switch to English to receive dynamic feedback
To give you one m x n Integer grid graph of grid , You can move from a grid to 4 Any lattice adjacent in two directions .
Please return to the grid from arbitrarily Grid departure , achieve arbitrarily lattice , And the number in the path is Strictly increasing Number of paths for . Because the answer could be big , Please correct the results 109 + 7 Remainder After the return .
If the grids accessed in the two paths are not exactly the same , Then they are regarded as two different paths .
Example 1：
![[leetcode Weekly game ] The first 300 site ——6110. The number of incremental paths in the grid graph - More difficult _leetcode Weekly game](/img/50/47bbb6080e5e864c9f1aa994fbc67a.png)
Example 2：
Tips ：
-
m == grid.length -
n == grid[i].length -
1 <= m, n <= 1000 -
1 <= m * n <= 105 -
1 <= grid[i][j] <= 105
Answer key
Method 1 ： Violent recursive solution
Ideas ：
It's simple , Violent recursive traversal , Unfortunately, I only came here 34/36 Test cases , The first 35 It's overtime . It hurts , For the first time in the week , The fourth question didn't pass because of timeout , A little unhappy ~~
For the first time in the week , Show ranking 1325~~, Take a screenshot and record it
![[leetcode Weekly game ] The first 300 site ——6110. The number of incremental paths in the grid graph - More difficult _ Net diagram _02](/img/8d/0e515af6c17971ddf461e3f3b87c30.png)
![[leetcode Weekly game ] The first 300 site ——6110. The number of incremental paths in the grid graph - More difficult _ Memorize _03](/img/ab/e7aa1e39916651d248428b8cb09a47.png)
class
Solution {
public:
int
mod
=
1e9
+
7;
void
path(
vector
<
vector
<
int
>>
&
grid,
int
x,
int
y,
int
&
res,
int
pre)
{
if (
y
>=
grid.
size()
||
x
>=
grid[
0].
size()
||
x
<
0
||
y
<
0)
{
return;
}
if (
grid[
y][
x]
<=
pre)
{
return;
}
res
= (
res
+
1)
%
mod;
int
cur
=
grid[
y][
x];
path(
grid,
x
-
1,
y,
res,
cur);
path(
grid,
x
+
1,
y,
res,
cur);
path(
grid,
x,
y
-
1,
res,
cur);
path(
grid,
x,
y
+
1,
res,
cur);
}
int
countPaths(
vector
<
vector
<
int
>>
&
grid)
{
if (
grid.
size()
==
0)
{
return
0;
}
if (
grid[
0].
size()
==
0)
{
return
0;
}
int
res
=
0;
vector
<
vector
<
int
>>
v(
grid.
size(),
std::vector
<
int
>(
grid[
0].
size(),
0));
for (
int
i
=
0;
i
<
grid.
size();
++
i)
{
for (
int
k
=
0;
k
<
grid[
0].
size();
++
k)
{
path(
grid,
k,
i,
res,
INT_MIN);
}
}
// return (res + grid.size() * grid[0].size()) % mod;
return
res;
}
};
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
Method 2 ： Memory resolution
Then I thought about it , Use an array to record the value of each path , When you have visited, just return directly . We use dp[y][x] Representation coordinates x、y All search paths for the coordinates of seven points . Tell the truth , This topic is really not difficult ~~~
The code is as follows ：
int
path(
vector
<
vector
<
int
>>
&
grid,
vector
<
vector
<
int
>>
&
v,
int
x,
int
y)
{
if (
y
>=
grid.
size()
||
x
>=
grid[
0].
size()
||
x
<
0
||
y
<
0)
{
return
0;
}
// If you have calculated , Then return directly
if (
v[
y][
x]
!=
0)
{
return
v[
y][
x];
}
int
direct[
4][
2]
= {
0,
1,
0,
-
1,
1,
0,
-
1,
0};
// Four search directions
v[
y][
x]
=
1;
// <--- Assume that the surrounding elements are no larger than it , only 1 A path
for (
int
i
=
0;
i
<
4;
++
i)
{
int
next_x
=
direct[
i][
0]
+
x;
int
next_y
=
direct[
i][
1]
+
y;
// Boundary condition check
if (
next_y
>=
grid.
size()
||
next_x
>=
grid[
0].
size()
||
next_x
<
0
||
next_y
<
0)
{
continue;
}
// Only incremental ones need to be calculated
if (
grid[
next_y][
next_x]
<=
grid[
y][
x])
{
continue;
}
v[
y][
x]
= (
v[
y][
x]
+
path(
grid,
v,
next_x,
next_y))
%
mod;
// Accumulate the adjacent lengths in four directions
}
return
v[
y][
x];
}
int
countPaths(
vector
<
vector
<
int
>>
&
grid)
{
int
res
=
0;
vector
<
vector
<
int
>>
v(
grid.
size(),
std::vector
<
int
>(
grid[
0].
size(),
0));
for (
int
i
=
0;
i
<
grid.
size();
++
i)
{
for (
int
k
=
0;
k
<
grid[
0].
size();
++
k)
{
res
= (
res
+
path(
grid,
v,
k,
i))
%
mod;
}
}
return
res;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
边栏推荐
- Zero length array
- Unity webgl optimization
- 2022-2028 global sepsis treatment drug industry research and trend analysis report
- 204. Count prime
- Closure and closure function
- 多媒体NFT聚合平台OKALEIDO即将上线，全新的NFT时代或将来临
- 企业级自定义表单引擎解决方案（十二）--表单规则引擎2
- Computer graduation design PHP campus address book telephone number inquiry system
- 简述服务量化分析体系
- [combinatorics] generating function (positive integer splitting | repeated ordered splitting | non repeated ordered splitting | proof of the number of repeated ordered splitting schemes)
猜你喜欢
Nodejs (01) - introductory tutorial
2022-2028 global sepsis treatment drug industry research and trend analysis report
How does GCN use large convolution instead of small convolution? (the explanation of the paper includes super detailed notes + Chinese English comparison + pictures)
leetcode：11. 盛最多水的容器【双指针 + 贪心 + 去除最短板】
English grammar_ Adjective / adverb Level 3 - multiple expression
What is SQL get connection
![[Yu Yue education] theoretical mechanics reference materials of Shanghai Jiaotong University](/img/52/b97c618a8f2eb29ad0ccca221bb5c1.jpg)
[Yu Yue education] theoretical mechanics reference materials of Shanghai Jiaotong University
Unity webgl optimization
SQL custom collation
![[untitled]](/img/83/5a57ed90aaafde94db600246256867.jpg)
[untitled]
随机推荐
[combinatorics] generating function (positive integer splitting | repeated ordered splitting | non repeated ordered splitting | proof of the number of repeated ordered splitting schemes)
Recommend a simple browser tab
English语法_名词 - 分类
Common PostgreSQL commands
Transformer T5 model read slowly
2022-2028 global aircraft head up display (HUD) industry research and trend analysis report
Niuke monthly race 31 minus integer
189. Rotation array
组策略中开机脚本与登录脚本所使用的用户身份
leetcode：556. 下一个更大元素 III【模拟 + 尽可能少变更】
Web3 credential network project galaxy is better than nym?
[combinatorics] generating function (use generating function to solve the number of solutions of indefinite equation)
Administrative division code acquisition
There are several levels of personal income tax
NFT新的契机，多媒体NFT聚合平台OKALEIDO即将上线
Real time split network (continuous update)
webcodecs
Kratos微服务框架下实现CQRS架构模式
[combinatorics] generating function (positive integer splitting | unordered non repeated splitting example)
Enterprise custom form engine solution (12) -- form rule engine 2