P1649 Obstacle Course S网页链接P1649 Obstacle Course S题目描述有一个N × N ( 1 ≤ N ≤ 100 ) N \times N(1 \le N \le 100)N×N(1≤N≤100)的场地场地由N 2 N^2N2个1 × 1 1 \times 11×1的方格组成。部分方格对于奶牛来说是无法通过的用x \texttt xx标记出来其他方格奶牛都可以通过用. \texttt ..标记出来。Bessie 发现自己位于这个场地中的位置A AA并且她想要移动到位置B BB去舔那里的盐块。像奶牛这种缓慢且笨拙的生物不喜欢转弯并且只能沿平行于方格边缘的方向移动。对于给定的场地求出从A AA到B BB的路径中最少的90 ∘ 90^{\circ}90∘转弯次数。路径可以从任何方向开始和结束。如果 Bessie 无法到达盐块的位置B BB请输出-1。输入格式第一行一个正整数N NN表示场地的长与宽。接下来N NN行每行一个长度为N NN的字符串字符串每个字符为{ x , . , A , B } \{\texttt{x},\texttt{.},\texttt{A},\texttt{B} \}{x,.,A,B}中的一种表示该方格的状态。输出格式一行一个整数表示 Bessie 必须进行的最小转弯次数。输入输出样例 #1输入 #13 . x A . . . B x .输出 #12说明/提示【样例1 11解释】Bessie 必须至少转弯两次例如Bessie 初始面朝南向南移动一步然后转身朝西再向西再移动两步接着转身朝南最后向南移动一步进入B BB方格。按照“上北下南左西右东”理解解题思路本题是带转弯代价的最短路径问题。奶牛只能沿网格方向移动求从起点A AA到终点B BB的最少90 ∘ 90^\circ90∘转弯次数。由于移动方向是离散的四个方向且转弯次数只与方向变化有关我们可以将“位置 当前方向”作为状态使用 BFS/最短路径算法求解。1. 问题等价转化状态定义设dis[x][y][d]表示从起点出发最终到达格子( x , y ) (x,y)(x,y)且面朝方向d dd时所需的最少转弯次数。方向d dd取值0 ∼ 3 0\sim30∼3分别对应右、下、左、上四个方向。初始状态从起点A AA可以向四个方向出发第一步不计算转弯因为题目允许从任何方向开始。因此对于每个方向d dd若( s x d x [ d ] , s y d y [ d ] ) (sxdx[d], sydy[d])(sxdx[d],sydy[d])在场地内且不是障碍则dis[该邻居][d] 0并加入队列。转移代价从状态( x , y , d ) (x,y,d)(x,y,d)尝试向四个方向移动若新方向n d ndnd与当前方向d dd相同则转弯次数不增加代价0 00若不同则发生一次90 ∘ 90^\circ90∘转弯代价1 11。更新dis[nx][ny][nd] min(dis[nx][ny][nd], dis[x][y][d] cost)。最终答案终点B BB可能以任意方向到达因此答案为min ⁡ d 0 3 dis [ B x ] [ B y ] [ d ] \min_{d0}^3 \text{dis}[B_x][B_y][d]mind03​dis[Bx​][By​][d]。若所有值仍为无穷大则输出− 1 -1−1。2. 算法实现本题代码使用BFS 队列优化类似 SPFA来求解带状态的最短路径初始化读入地图记录起点A AA、终点B BB障碍标记mp[i][j]1。将所有dis初始化为INF。对四个方向d dd若A AA的邻居合法则入队dis[邻居][d]0。BFS 扩展从队列取出状态(tx,ty,dt)。枚举四个方向i ii计算新位置(xx,yy)。若新位置越界或为障碍跳过。计算代价c (dt i ? 0 : 1)。若dis[xx][yy][i] dis[tx][ty][dt] c则更新并入队若尚未入队。出队时将vis标记清空允许后续再次入队更新更优值。答案输出遍历四个方向取dis[ex][ey][d]的最小值。若为INF输出-1否则输出该值。3. 复杂度分析时间复杂度状态总数为O ( N 2 × 4 ) O(N^2 \times 4)O(N2×4)每个状态最多被更新入队若干次。由于N ≤ 100 N \le 100N≤100状态量约4 × 10 4 4\times 10^44×104即使采用 SPFA 式重复入队也可在极短时间内完成。空间复杂度O ( N 2 × 4 ) O(N^2 \times 4)O(N2×4)存储距离数组和访问标记空间消耗很小。总结将方向作为状态维度通过 BFS 在扩展时比较方向是否变化来累加转弯次数即可求得最少转弯次数。初始时直接枚举四个方向进入起点邻居等价于允许起点方向任意巧妙处理了“路径可以从任何方向开始”的规则。代码简要说明方向数组dx[4] {0,1,0,-1}和dy[4] {1,0,-1,0}分别表示右、下、左、上。dis[x][y][d]到达(x,y)且方向为d的最少转弯次数。初始从A AA的四个邻居入队方向为对应方向距离设为0 00。BFS 过程中若方向变化则距离加1 11否则加0 00。最后取终点四个方向的最小值输出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll dx[4]{0,1,0,-1};constll dy[4]{1,0,-1,0};ll n;ll sx,sy,ex,ey,c,ansINF;ll mp[105][105];ll dis[105][105][5];boolvis[105][105][5];structpoint{ll x,y,dt;};queuepointq;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i)for(ll j1;jn;j){charch;cinch;if(chA){sxi;syj;}if(chB){exi;eyj;}if(chx)mp[i][j]1;}for(ll i1;in;i)for(ll j1;jn;j)for(ll k0;k4;k)dis[i][j][k]INF;for(ll i0;i4;i){ll xxsxdx[i],yysydy[i];if(xx1||yy1||xxn||yyn||mp[xx][yy])continue;vis[xx][yy][i]1;point a;a.xxx;a.yyy;a.dti;q.push(a);dis[xx][yy][i]0;}while(!q.empty()){point tq.front();q.pop();ll txt.x,tyt.y;for(ll i0;i4;i){ll xxtxdx[i],yytydy[i];if(xx1||yy1||xxn||yyn||mp[xx][yy])continue;if(t.dti)c0;elsec1;if(dis[xx][yy][i]dis[tx][ty][t.dt]c){dis[xx][yy][i]dis[tx][ty][t.dt]c;if(!vis[xx][yy][i]){point a;a.xxx;a.yyy;a.dti;q.push(a);vis[xx][yy][i]1;}}}vis[tx][ty][t.dt]0;}for(ll i0;i4;i)ansmin(ans,dis[ex][ey][i]);if(ansINF)cout-1\n;elsecoutansendl;return0;}