解题思路与方法

动态规划

我们令 dp[i][j] 表示从起点 (1,1) 到达格子 (i,j) 的方案数。因为只能向下或向右走，状态转移方程为：

dp[i][j] = 
如果 (i,j) 是障碍，dp[i][j]=0  
否则 dp[i][j]=(dp[i-1][j] + dp[i][j-1]) mod M

边界条件：

题目内容

在 $n*n$ 的网格中，牛牛家在第 $1$ 行第 $1$ 列（左上角），青牛小学在第 $n$ 行第 $n$ 列（右下角）。 牛牛从家里出发，每一步可以往下或往右走，最终走到青牛小学。 在网格中，有两个位置都有一个障碍物，牛牛不能走到这两个位置。 牛牛从家里走到青牛小学的方案数是多少？

输入描述

第一行一个整数 $n$，表示网格的大小。

第二行两个整数 $x_1,y_1$，表示第一个障碍物在第$x_1$行$y_1$列。

第三行两个整数 $x_2,y_2$，表示第二个障碍物在第$x_2$行$y_2$列。

$1\leq n\leq 1000,1\leq x_1,y_1,x_2,y_2\leq n$

保证两个障碍物不在同一个位置。保证两个障碍物都不在牛牛家和青牛小学。

输出描述

输出一个整数，表示方案数。 由于结果可能很大，答案对 $998244353$ 取模再输出。

示例1

输入

3
1 3
2 1

输出

2

示例2

输入

5
1 2
3 4

输出

23

示例3

输入

5
1 4
2 3

输出

35

示例4

输入

3
3 1
2 1

输出

3