题解 AT4529 【Grid 1】

· · 题解

解题思路

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int INF = 1e9+7;
char a[maxn][maxn];
bool vis[maxn][maxn];
long long ans = 0,h,w;

bool inside(int i,int j) {
    if(i <= 0 || i > h || j <= 0 || j > w) return false;
    return true;
}

void dfs(int i,int j) {
    if(i == h && j == w) {
        ans = (ans + 1) % (INF);
        return;
    }
    if(inside(i+1,j) && a[i+1][j] != '#') 
        dfs(i+1,j);
    if(inside(i,j+1) && a[i][j+1] != '#') 
        dfs(i,j+1);
}

int main() {
    cin>>h>>w;
    for(int i = 1;i <= h;i++) {
        scanf("%s",a[i]+1);
    }
    dfs(1,1);
    cout<<ans;
    return 0;
}

RE了，很明显搜索行不通，换dp

本题是二维矩阵下的方案dp

dp数组:dp[i][j]代表从起点1,1到i,j位置的方案数,

dp边界：dp[1][1] = 1（记住方案dp，一般不动也是一个方案）,因为从（1,1）位置只能向右走或者向下走，我们试着把以（1,1）点为中心的横纵左边的初始状态也求出来，记住及时break

状态转移： 递推方向为i从2->h,j从2->w。显然可以得到状态转移方程为

dp[i][j] = (dp[i-1][j] + dp[i][j-1]) (a[i][j] == '.')

实现：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1100;
const int INF = 1e9+7;
char a[maxn][maxn];
int dp[maxn][maxn];     //dp[i][j]´ú±íÖÕµãΪi,jµÄ·½°¸Êý 
bool vis[maxn][maxn];
long long ans = 0,h,w;

int main() {
    cin>>h>>w;
    for(int i = 1;i <= h;i++) {
        scanf("%s",a[i]+1);
    }
    for(int i = 1;i <= w;i++) {
        if(a[1][i] == '.') dp[1][i] = 1;
        else break;
    }
    for(int i = 1;i <= h;i++) {
        if(a[i][1] == '.') dp[i][1] = 1;
        else break;
    }

    for(int i = 2;i <= h;i++) {
        for(int j = 2;j <= w;j++) {
            if(a[i][j] == '.') {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % INF;
            }
        }
    }
    cout<<dp[h][w];
    return 0;
}