Codeforces 173B

双端队列bfs

题意：

一个 的图，现在有一束激光从左上角往右边射出，每遇到 '#'，你可以选择光线往四个方向射出，或者什么都不做，问最少需要多少个 '#' 往四个方向射出才能使光线在第 行往右边射出。
此题目正解不是 0-1 BFS 但是适用 0-1 BFS 可以不需要思考过程，赛时许多大佬都是这么做的。
做法很简单，一个方向射出不需要花费（0），而往四个方向射出需要花费（1），然后直接来就可以了。

适用条件：0-1图

#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 29)
int n, m;
char grid[1001][1001];
int dist[1001][1001][4];
int vis[1001][1001][4];
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
deque<int> q;

void add_front(int x,int y,int dir,int d){
    if(dist[x][y][dir]>d){
        dist[x][y][dir]=d;
        q.push(dir);
        q.push(y);
        q.push(x);
    }
}

void add_back(int x,int y,int dir,int d){
    if(dist[x][y][dir]>d){
        dist[x][y][dir]=d;
        q.push(x);
        q.push(y);
        q.push(dir);
    }
}

int main(){
    cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> grid[i];

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      for (int k = 0; k < 4; k++) dist[i][j][k] = INF;

      add_front(n - 1, m - 1, 3, 0);

    while (!q.empty()) {
    int x = q[0], y = q[1], dir = q[2];
    q.pop_front();
    q.pop_front();
    q.pop_front();
    if (vis[x][y][dir]) continue;
    vis[x][y][dir] = true;
    int d = dist[x][y][dir];
    int nx = x + fx[dir], ny = y + fy[dir];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m) add_front(nx, ny, dir, d);
    if (grid[x][y] == '#')
      for (int i = 0; i < 4; i++)
        if (i != dir) add_back(x, y, i, d + 1);
  }
  if (dist[0][0][3] == INF)
    cout << -1 << endl;
  else
    cout << dist[0][0][3] << endl;
  return 0;

}