题解 | #「木」迷雾森林#

哎呦我操帕秋莉怎么这么坏啊

这题直接浪费了我大好的一个上午加中午的学习时间，我现在正在一边啃着我最爱的腰果一边控诉这道题：

思路上很明显，虽然说这题一股子BFS味，但是为了求所有方式，复杂度上DFS又不合适，我们自然而然想到了DP。“情况”也很明显——不同位置走到的方式，同时只能向上向右走又保证了有单调性。思路就这么简单。这道题本身也是超级无敌的板子题，熟悉DP用的

但！是！有三点必须注意！

1，他虽然给了快读模板，但这种还是自己备用一个比较合适，我备用的是这个：

string read()
{
    string ss;
    
    char ch = getchar();
    
    while(ch=='\n'||ch=='\r'||ch==' ') ch=getchar();
    
    while(ch!='\n'&&ch!='\r')
    {
        if(ch!=' ') ss+=ch;
        
        ch=getchar();
        
        if(ch==EOF) break;
    }
    return ss;
}

2：我们一定要先把段错误限制条件给写在前面啊！

if(r + 1 < m && dp[r + 1][p] >= 0)——对

if(dp[r + 1][p] >= 0 && r + 1 < m)——错

这个是大一上就学过的知识点，这是我的问题，我反思自己.jpg

3：我们取MOD，一定要注意每一步都要取MOD！（25%，我就是因为这个被硬控了）

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

string read()
{
    string ss;
    
    char ch = getchar();
    
    while(ch=='\n'||ch=='\r'||ch==' ') ch=getchar();
    
    while(ch!='\n'&&ch!='\r')
    {
        if(ch!=' ') ss+=ch;
        
        ch=getchar();
        
        if(ch==EOF) break;
    }
    return ss;
}

signed main() 
{ 
    int m,n;
    
    cin>>m>>n;
    
    vector<vector<int>> dp(m,vector<int>(n,0));
    
    for(int r = m - 1;r >= 0;r--)
    {
        string temp = read();
        
        for(int p = 0;p < n;p++)
        {
            if(temp[p] == '1')
            {
                dp[r][p] = -1;//这里用LLONG_MIN会导致全部变为0？
            }
        }
    }
    
    dp[0][0] = 1;
    
    for(int r = 0;r < m;r++)
    {
        for(int p = 0;p < n;p++)
        {
            if(dp[r][p] >= 0)
            {
                if(r + 1 < m && dp[r + 1][p] >= 0)
                {
                    dp[r + 1][p] += dp[r][p];
                    
                    dp[r + 1][p] = dp[r + 1][p] % 2333;
                }
                
                if(p + 1 < n && dp[r][p + 1] >= 0)//唉又写反了
                {
                    dp[r][p + 1] += dp[r][p];
                    
                    dp[r][p + 1] = dp[r][p + 1] % 2333;
                }
            }
        }
    }
    
    cout<<(dp[m - 1][n - 1] % 2333)<<endl;
    
    return 0;
}