牛客周赛37

E - 魔法之森的蘑菇

题目描述

给定一张网格图，起点为 $S$，终点为 $T$。起初可以任选一个前进方向；除非遇到 *，否则不能改变方向。遇到 * 时，可以选择除“返回刚刚来的方向”以外的其他方向。# 为障碍，. 为普通路径，求从 $S$ 到 $T$ 的最短距离。

分析

一开始容易想到普通 BFS：遇到 * 就把三个可选方向都加入队列，遇到 . 就沿原方向继续走。

但这个题的状态不能只记录位置。到达同一个点时，不同的进入方向会影响后续能否转向，因此状态应该是：

$$(x,y,dir)$$

也就是位置加方向。每个点需要维护四个方向上的最短距离，本质上是一个按方向分层的最短路问题。

另一题：按位与 DP

分析

状态可以设计为：

$$dp[i][j]$$

表示考虑前 $i$ 个数时，按位与结果为 $j$ 的最小选择个数。转移为：

$$dp[i][a_i\&j]=\min(dp[i][a_i\&j], dp[i-1][j]+1)$$

由于相同的数进行按位与后结果不会变成 $0$，可以先统计 $0\sim127$ 中出现过的值，并使用滚动数组优化空间。

滚动后的转移为：

$$dp_1[i\&j]=\min(dp_1[i\&j], dp_0[j]+1)$$

E 题代码

int n, m, sx, sy, ex, ey, len[N][N][4], dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
bool st[N][N][4];
char g[N][N];
queue> q;
void solve()
{
    while (q.size())
        q.pop();
    cin >> n >> m;
    for (int i = 1; i > g[i][j];
            if (g[i][j] == 'S')
                sx = i, sy = j, g[i][j] = '*';
            if (g[i][j] == 'T')
                ex = i, ey = j, g[i][j] = '*';
        }
    for (int i = 0; i = 1 && t = 1 && z = 1 && t = 1 && z = 1 && t = 1 && z

按位与 DP 代码

int dp[2][203],p[220];//滚动数组和记录0~127数存在与否的p
void solve(){
    int n;cin>>n;
    memset(p,0,sizeof p);
    for(int i=1;i>x;
        p[x]++;
    }
    memset(dp,0x3f,sizeof dp);
    for(int i=0;in)cout<<-1<<"\n";
    else cout<<n-dp[0][0]<<"\n";//求得组成当前数最小个数，所以抛弃个数为n-dp[0][0]
}