原题大意

bfs搜索题，从左上角到右下角，必须走在有灯的格子里，如果要去的格子没有灯，可以暂时照亮任意一行或者一列，但必须之前站在原来就是有灯的格子里，同时花费为1，问是否能到达目的地，如果能输出最小花费，否则输出-1。

算法分析

每次bfs都是在原始就是有灯的点之间移动（除了终点）

一行或者一列最多被照亮一次

当前点，与下一次可以到达的点的横坐标或纵坐标距离小于等于2

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a));
#define pb push_back
using namespace std;
const int maxn = 10000 + 50;
const int MAXN = (1<<30);
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
priority_queue<pii, vector<pii>, greater<pii> > pq;
map<pii, int> label;
vi r[maxn], c[maxn];
vector<pii> lights;
bool dr[maxn], dc[maxn];
int dirx[4] = {0,-1,0,1};
int diry[4] = {-1,0,1,0};
int dist[maxn];
int n, m, k;
void Init(){
  while(!pq.empty()) pq.pop();
  label.clear();
  for(int i = 0; i < maxn; i++){
    r[i].clear();
    c[i].clear();
    dist[i] = MAXN;
    dr[i] = dc[i] = false;
  }
    lights.clear();
}
void filrow(int row, int val){
  if(row >= 1 && row <= n && !dr[row]){
    dr[row] = true;
    for(auto x : r[row]) if(dist[x] > val){
      dist[x] = val;
      pq.push({dist[x], x});
    }
  }
}
void filcol(int col, int val){
  if(col >= 1 && col <= m && !dc[col]){
    dc[col] = true;
    for(auto y : c[col]) if(dist[y] > val){
      dist[y] = val;
      pq.push({dist[y], y});
    }
  }
}
void ad(int x, int y, int val){
  if(label.find({x, y}) != label.end()){
    if(dist[label[{x, y}]] > val) {
      dist[label[{x, y}]] = val;
      pq.push({val, label[{x, y}]});
    }
  }
}
int main(){

  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  while(cin >> n >> m >> k){
    Init();
    for(int i = 0; i < k; i++){
      int x, y;
      cin >> x >> y;
      r[x].pb(i);
      c[y].pb(i);
      lights.pb({x, y});
      label[{x, y}] = i;
    }
    if(label.find({n, m}) == label.end()){
      filrow(n, 1);
      filrow(n-1, 1);
      filcol(m, 1);
      filcol(m-1, 1);
    }else pq.push({0, label[{n, m}]});

    while(!pq.empty()){
      auto a = pq.top();pq.pop();
      int d = a.first;
      int p = a.second;
      if(d > dist[p]) continue;
      for(int i = 0; i < 4; i++) 
        ad(lights[p].first + dirx[i], lights[p].second + diry[i], d);
      for(int i = lights[p].first - 2; i <= lights[p].first + 2; i++)
        filrow(i, d+1);
      for(int i = lights[p].second - 2; i <= lights[p].second + 2; i++)
        filcol(i, d+1);
    }
    if(dist[0] == MAXN) cout << "-1" << endl;
    else cout << dist[0] << endl;
  }
  return 0;
}