有一个n×nn×nn×n的网格，有些格子是可以通行的，有些格子是障碍。

一开始你在左上角的位置，你可以每一步往下或者往右走，问有多少种走到右下角的方案。

由于答案很大，输出对109+710^9+7109+7取模的结果。

输入格式

第一行一个正整数nnn。

接下来nnn行，每行nnn个正整数，111表示可以通行，000表示不能通行。

输出格式

一个整数，表示答案。

样例输入

3
1 1 1
1 0 1
1 1 1

样例输出

2

数据规模

对于100100100%的数据，保证2≤n≤1002≤n≤1002≤n≤100，左上角右下角都是可以通行的。

解题思路：

这是一道动态规划题目（和没说一样）

每个格子的到达方式只有两种，要么从左侧，要么从上方

所以要知道到达map[n][n]的方法数，只需要知道到达map[n - 1][n]和map[n][n - 1]的方法数即可

依此类推，再考虑一下障碍物的存在，动态规划的状态转移方程就有了

map[i][j] = (map[i - 1][j] * obstacle[i - 1][j]+ map[i][j - 1] * obstacle[i][j - 1]) % mod_num;

*注：其中obstacle[i][j]为0代表可以通行，为1代表不可通行

那么如何遍历呢？

要求是在到达map[i][j]之前，已经到达过map[i - 1][j]和map[i][j - 1]

只需要二重循环就可以了

最后，AC代码如下

#include 
using namespace std;
const int max_n = 100;
const int mod_num = 1e9 + 7;int n;
int map[max_n + 1][max_n + 1];
bool obstacle[max_n + 1][max_n + 1];int main() {map[1][1] = 1;//初始化：到达起点方法数为1cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> obstacle[i][j];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {map[i][j] = (map[i - 1][j] * obstacle[i - 1][j]+ map[i][j - 1] * obstacle[i][j - 1]) % mod_num;}}cout << map[n][n];return 0;
}