Switch the lamp on

BFS与双端队列

#include<bits/stdc++.h>
using namespace std;
const int dir[4][2] = {{-1,-1},{-1,1},{1,-1},{1,1}};     //4个方向的位移：器
const int ab[4] = {2,1,1,2};                             //4个元件期望的方向
const int cd[4][2] = {{-1,-1},{-1,0},{0,-1},{0,0}};      //4个元件编号的位移：节点，田
int graph[505][505],dis[505][505];                       //dis记录结点到起点s的最短路
  struct P{ int x,y,dis; }u;                             //记录坐标加上当前节点最短路
  int read_ch(){                                         //读取地图转换成数字
  char c;
  while((c = getchar())!='/' && c != '\\') ;             //字符不是'/'和'\'
  return c=='/' ? 1 : 2;
}
int main(){
  int n, m; cin >>n >>m;
  memset(dis,0x3f,sizeof(dis));                           //初始化
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j) graph[i][j] = read_ch();
  deque <P> dq;
  dq.push_back((P){1,1,0});                               //入口入队
  dis[1][1] = 0;
  while(!dq.empty()){
    u = dq.front(), dq.pop_front();                       //front()读队头,pop_front()弹出队头
    int nx,ny;
    for(int i=0;i<=3;++i) {                               //4个方向
      nx = u.x+dir[i][0]; ny = u.y+dir[i][1];
      int d = 0; //边权
      d = graph[u.x+cd[i][0]][u.y+cd[i][1]]!=ab[i];       //中间节点：若方向不相等,则d=1
      if(nx && ny && nx<n+2 && ny<m+2 && dis[nx][ny]>dis[u.x][u.y]+d){         //不出界+贪心
        dis[nx][ny] = dis[u.x][u.y]+d;                    //更新当前节点最短路
        if(d==0) dq.push_front((P){nx, ny, dis[nx][ny]});                      //边权=0，插到队头
        else dq.push_back ((P){nx, ny, dis[nx][ny]});     //边权=1，插到队尾
        if(nx==n+1 && ny==m+1) break;                                          //到终点退出。不退也行，队列空自动退
      }
    }
  }
  if(dis[n+1][m+1] != 0x3f3f3f3f) cout << dis[n+1][m+1];
  else cout <<"NO SOLUTION";                               //可能无解，即s到t不通
  return 0;
}

笔记：边权为0或者1的特殊图，用双端队列搜索时间更快，边权为0的放在队头，先搜索，边权为1的放在队尾后搜索，它的拓展邻居也是比较特殊，是四个角对角线上的邻居，线段交会的伪节点寻找最短路径