题目描述
线现在在一个地图上，它正在(1,1)上（左上角），最终要去到(M,N)上。它不但只能往下或往右走，还只能在整数格子上移动。
Imakf有的时候想要炫技，又有时想偷懒，所以他会告诉你这张地图的全貌，你要告诉他到达终点的最多和最少拐弯次数。
分析
一开始写这道题目的时候，比较早，所以就不会往DP的方向想。
我一开始跑了一个三元组的dijkstra，(i,j,k)表示出于(i,j)的格子，然后面向方向是k（k[0..1]），的最大拐弯数。
和最小的拐弯数，成功60分，也不知道怎么回事。WA了那一点是因为没有判断一开始的节点是不是非法的。
但是后面莫名TLE，这是为什么我都不知道。可能我成功把dijkstra变成了dfs吧（听说DFS是超时的）。
附上比赛时候自己写的代码。。。
// luogu-judger-enable-o2
# include <bits/stdc++.h>
# define Inf 0x7fffffff
# define Ri register int
# define for1(i,a,b) for (Ri i(a);i <= b; ++i)
# define for2(i,a,b) for (Ri i(a);i >= b; --i )
using namespace std;
const int dx[2] = { 1 , 0 };
const int dy[2] = { 0 , 1 };
inline int read ()
{
int w = 0,x = 0; char ch = 0;
while ( !isdigit(ch) ) { w |= ch == '-'; ch = getchar() ; }
while ( isdigit(ch) ) { x = (x<<1) + (x<<3) + (ch^48); ch = getchar() ; }
return w ? -x : x ;
}
struct node1{
int x, y ,dis ,dir;
friend bool operator<(node1 a,node1 b)
{
return a.dis<b.dis;
}
};
struct node2{
int x, y ,dis ,dir;
friend bool operator<(node2 a,node2 b)
{
return a.dis>b.dis;
}
};
const int Maxn = 1005;
int n , m;
int dist1[Maxn][Maxn][2], dist2[Maxn][Maxn][2];
int a[Maxn][Maxn];
inline void dijkstra1()
{
priority_queue<node1>q;
while (!q.empty()) q.pop();
for1(i ,1 ,n ) for1(j ,1 ,m ) for1(k ,0 ,1 ) dist1[i][j][k] = 0;
for1(i ,0 ,1 ) q.push((node1) {1,1,0,i});
while (!q.empty())
{
node1 u=q.top();
q.pop();
if (u.dis < dist1[u.x][u.y][u.dir] ) continue;
for1 (i, 0, 1)
{
int nx = u.x + dx[i], ny = u.y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if ( a[nx][ny] == 0 ) continue;
int cc = 0;
if (u.dir != i) cc = 1;
if ( dist1[nx][ny][i] < u.dis + cc)
{
dist1[nx][ny][i] = u.dis + cc;
q.push((node1){nx, ny, dist1[nx][ny][i], i});
}
}
}
}
inline void dijkstra2()
{
priority_queue<node2>q;
while (!q.empty()) q.pop();
for1(i ,1 ,n ) for1(j ,1 ,m ) for1(k ,0 ,1 ) dist2[i][j][k]=Inf;
for1(i ,0 ,1 ) q.push((node2){1,1,0,i});
while (!q.empty())
{
node2 u=q.top();
q.pop();
if (u.dis > dist2[u.x][u.y][u.dir] ) continue;
for1 (i, 0, 1)
{
int nx = u.x + dx[i], ny = u.y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if ( a[nx][ny] == 0 ) continue;
int cc = 0;
if (u.dir != i) cc = 1;
if ( dist2[nx][ny][i] > u.dis + cc)
{
dist2[nx][ny][i] = u.dis + cc;
q.push((node2){nx, ny, dist2[nx][ny][i], i});
}
}
}
}
int main ()
{
n = read() ,m = read() ;
for1 (i ,1 ,n )
{
char s[1005];
scanf("%s",s);
for1 (j ,0 ,m )
{
if (s[j]=='o') a[i][j+1] = 1;
else a[i][j+1] = 0;
}
}
dijkstra1(); dijkstra2();
int ans1 = 0 , ans2 = Inf;
for1 (i ,0 ,1 ) ans1 = max(ans1 , dist1[n][m][i] ),ans2 = min(ans2, dist2[n][m][i]);
if (ans1 == 0 && ans2 == Inf ) printf ("-1\n");
else printf ("%d %d\n", ans1-1, ans2);
return 0;
}100pt
满分做法就是DP了，状态也非常好想到就是我们上面提到的三元组，将其转化成状态就可以了。
f[i][j][k]表示在(i,j)的格子上，面朝方向是k的(0..1)（0代表面朝下面，1表示面朝右边）时的最小答案。
g[i][j][k]表示在(i,j)的格子上，面朝方向是k的(0..1)（0代表面朝下面，1表示面朝右边）时的最小答案。
那么转移方程也是非常好写的。
我们先考虑(i-1,j) 转移到(i,j)那么一定是往下走，那么只能推到f[i][j][0]的状态。
那么就判断一下，如果原来的k是0的话，那么步数+1。否则就是直接推过来。
那么第二种情况就是从(i,j-1)走过来，那么一定是往右边走，那么只能推到f[i][j][1]的状态。
接下来的转移和上方一样。
不要忘记判断起点是#的情况。
而且如果不是用深搜判断，那么就不能用全用or判断，因为结尾方向可能只有一个。必须用and。
ac代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 1005
using namespace std;
char s[N];
int f[N][N][2], g[N][N][2];
int a[N][N];
int n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) {
scanf("%s", s);
int len = strlen(s);
for (int j = 0; j < len; j ++) {
if (s[j] == 'o') a[i][j + 1] = 0;
else a[i][j + 1] = 1;
}
}
if (a[1][1]) {
printf("-1");
return 0;
}
memset(f, inf, sizeof(f));
memset(g, -inf, sizeof(g));
f[1][1][0] = f[1][1][1] = g[1][1][1] = g[1][1][0] = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (a[i][j]) continue;
if (i > 1) {
f[i][j][0] = min(f[i][j][0], f[i - 1][j][1] + 1);
f[i][j][0] = min(f[i][j][0], f[i - 1][j][0]);
g[i][j][0] = max(g[i][j][0], g[i - 1][j][1] + 1);
g[i][j][0] = max(g[i][j][0], g[i - 1][j][0]);
}
if (j > 1) {
f[i][j][1] = min(f[i][j][1], f[i][j - 1][0] + 1);
f[i][j][1] = min(f[i][j][1], f[i][j - 1][1]);
g[i][j][1] = max(g[i][j][1], g[i][j - 1][0] + 1);
g[i][j][1] = max(g[i][j][1], g[i][j - 1][1]);
}
}
}
if ((g[n][m][1] == -inf && g[n][m][0] == -inf) || (f[n][m][1] == inf && f[n][m][0] == inf)) printf("-1\n");
else printf("%d %d\n", max(g[n][m][1], g[n][m][0]) - 1, min(f[n][m][1], f[n][m][0]));
return 0;
}