2852: 小A的通勤系列二
时间限制: 1 Sec 内存限制: 128 MB
提交: 98 解决: 21
[状态] [讨论版] [提交] [命题人:541703040109]
题目描述
小A下了地铁需要经过一个公园才到公司，小A经过的公园是一个长N宽M的矩形，小A每天从左下角进入公园，从右上角走出公园。这天小A下地铁比较早，想计算一下从进入公园到走出公园一共有多少种方式？为了不浪费时间，小A总是向上或者向右移动。
小A经过查阅，公园内只有可行走的道路和不可行走的花园。小A将公园地图记录下来，使用符号代替，S代表起点，E代表终点，.代表道路，#代表花园。
输入
第一行输入两个整数N,M分别代表公园的长和宽 2<=N,M<=1000
接下来输入N行，每行输入M个字符，代表公园的地图。
输出
输出一个整数，代表小A有多少种方式走出公园。结果对998244353取模。
样例输入 Copy
3 4 ...E .#.. S... 样例输出 Copy
4
思路：
看了看数据，有点大，开始艰难dp，
首先只能从下方和左方来到当前位置，于是方程为
a[i][j]=a[i+1][j]+a[i][j-1]
需要特判的位置注意下特判即可，记得取模！！
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define met(a,b) memset(a,b,sizeof a)
#define y second
#define x first
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
using namespace std;
const int N=1e6+10;
typedef long long ll;
const int mod = 998244353;
string s[1005];
ll a[1005][1005];
int main() {
met(a,0);
int n,m;
cin>>n>>m;
int f=0;
for(int i=0; i<n; i++)cin>>s[i];
for(int i=n-1; i>=0; i--) {
for(int j=0; j<m; j++) {
if(s[i][j]=='#') {
a[i][j]=0;
continue;
}
if(s[i][j]=='S') continue;
if(s[i][j]=='E') {
a[i][j]=(a[i+1][j]+a[i][j-1])%mod;
f=1;
break;
}
if(i==n-1&&j==1||i==n-2&&j==0) {
a[i][j]=1;
continue;
}
if(j==0) {
a[i][j]=a[i+1][j];
continue;
}
if(i==n-1) {
a[i][j]=a[i][j-1];
continue;
}
a[i][j]=(a[i+1][j]+a[i][j-1])%mod;
}
if(f)break;
}
cout<<a[0][m-1];
return 0;
}