题解 AT4529 【Grid 1】

houpingze

一道非常简单的dpqwq

当f_{i,j}不是#（障碍物）的时候：

即：
f_{i,j}=f_{i-1,j}+f_{i,j-1}

如果是障碍物，f_{i,j}自然为0

code:

#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
	int res=0,fs=1; char c=getchar();
	while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
	while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
	return res*fs;
}
void print(int x){
    if(x<0) { putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,cnt,m,a[5010],ans,tmp;
char mp[1105][1005];
//mp数组是地图
int f[1005][1005];
//f[i][j]表示走到（i,j）的方案数
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j]; 
		}
	}
	f[1][1]=(mp[1][1]!='#');//注意起点
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i==1&&j==1) continue;
			f[i][j]=f[i-1][j]+f[i][j-1];
			f[i][j]%=1000000007;//别忘记取模！
			if(mp[i][j]=='#') f[i][j]=0;//有障碍物，直接设为0
		}
	}
	cout<<f[n][m];
    return 0;
}