挺水的棋盘dp题目类型
虽然说水，但是我今晚快一个多小时卡在这道题上面。这反映了我对这类dp的不熟悉。
这道题一看上去就知道应该是要dp的，每一步只能走右或走下就已经提示给你要这么转移。
做dp首先想明白怎么定义状态：
设dp[i][j][0/1]表示当前走到\(i\)行\(j\)列，目前的朝向向右(0)或向下(1)的最大或最小操作数。
这里是我最没有想到的转移环节：
当目前朝向朝右的时候，你只能够从\((i,j-1)\)这个点处转移来，决策就两个：拐弯或不拐弯。
同理，当现在朝下的时候只能从她上面转移而来。
这样，每一个点的转移就只有两个取值。
当然，障碍我们就不用转移了，直接忽略掉让她是memset上的极大值或极小值就可以了。
最后如何判断有解？
我的做法是判断那个最大的步数是否大于0，因为初始化是极小值，所以如果不大于0就无法到达。
当然也可以开局就跑个dfs来专门判断。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::min;
const int maxn = 1005;
const int _INF = -1886417009;
const int INF = 0x3f3f3f3f;
int dpmax[maxn][maxn][2];// 0: right, 1: down
int dpmin[maxn][maxn][2];
char ch[maxn][maxn];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%s", ch[i] + 1);
}
memset(dpmax, 0x8f, sizeof dpmax);
memset(dpmin, 0x3f, sizeof dpmin);
for(int i = 1; i <= n; i++)
{
if(ch[i][1] == '#') break;
dpmax[i][1][1] = dpmin[i][1][1] = 0;
dpmax[i][1][0] = dpmin[i][1][0] = 1;
}
for(int i = 1; i <= m; i++)
{
if(ch[1][i] == '#') break;
dpmax[1][i][0] = dpmin[1][i][0] = 0;
dpmax[1][i][1] = dpmin[1][i][1] = 1;
}
for(int i = 2; i <= n; i++)
{
for(int j = 2; j <= m; j++)
{
if(ch[i][j] == '#') continue;
dpmax[i][j][0] = max(dpmax[i][j-1][1] + 1, dpmax[i][j-1][0]);
dpmax[i][j][1] = max(dpmax[i-1][j][0] + 1, dpmax[i-1][j][1]);
dpmin[i][j][0] = min(dpmin[i][j-1][1] + 1, dpmin[i][j-1][0]);
dpmin[i][j][1] = min(dpmin[i-1][j][0] + 1, dpmin[i-1][j][1]);
}
}
int maxans = max(dpmax[n][m][0], dpmax[n][m][1]);
int minans = min(dpmin[n][m][0], dpmin[n][m][1]);
if(maxans < 0) printf("-1\n");
else printf("%d %d\n", maxans, minans);
/*
while(233)
{
int x, y, z; scanf("%d%d%d", &x, &y, &z);
printf("%d\n", dpmax[x][y][z]);
}
*/
return 0;
}