STL+BFS做法

AC历程 也是AC得很坎坷。

思路：

• 使用vector+map记录每一面镜子的坐标。注意：因为每一行每一列可能会有多个镜子，又行列坐标范围太大，我们需要用map离散化。
• 将终点也看作一面镜子加入其中，最后统计答案时-1即可。
• 主要有两项剪枝：
  1. 如果当前镜子的其中一个坐标与终点的一个坐标相对应，那么将它加入到队头。
  2. 如果当前行或列的镜子被遍历过，那么跳过，因为肯定加入过队列。

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef pair<int, int> PII;
const int N=1e6+10;
int n; bool vc[N], vr[N];
unordered_map<int, int> c, r;
vector<int> col[N], row[N];
struct node{int x, y;} st, ed;
struct type{int x, y, op, res;};
map<PII, bool> mp[2];
void bfs() {
	int ans=0; 
	deque<type> q;
	q.push_back({st.x, st.y, 0, 0});
	q.push_back({st.x, st.y, 1, 0});
	mp[1][{st.x, st.y}]=true;
	mp[0][{st.x, st.y}]=true;
	while(!q.empty()) {
		auto x=q.front(); q.pop_front();
		if(x.x==ed.x&&x.y==ed.y) {ans=x.res-1; break;}
		if(x.op==0) {
			if(vc[c[x.x]]) continue; vc[c[x.x]]=true;
			for(auto i:col[c[x.x]]) {
				if(!mp[0][make_pair(x.x, i)]) {
					if(i==ed.y) q.push_front({x.x, i, 1, x.res+1});
					else q.push_back({x.x, i, 1, x.res+1});
					mp[0][make_pair(x.x, i)]=true;
				}
			}
		}
		else {
			if(vr[r[x.y]]) continue; vr[r[x.y]]=true;
			for(auto i:row[r[x.y]]) {
				if(!mp[1][make_pair(i, x.y)]) {
					if(i==ed.x) q.push_front({i, x.y, 0, x.res+1});
					else q.push_back({i, x.y, 0, x.res+1});
					mp[1][make_pair(i, x.y)]=true;
				}
			}
		}
	}
	printf("%d\n", ans);
}
int main() {
	scanf("%d", &n);
	scanf("%d%d%d%d", &st.x, &st.y, &ed.x, &ed.y);
	for(int i=1;i<=n;i++) {
		int x, y; scanf("%d%d", &x, &y);
		if(c[x]==0) c[x]=i;  if(r[y]==0) r[y]=i;
		col[c[x]].push_back(y); row[r[y]].push_back(x);;
	}
	if(c[ed.x]==0) c[ed.x]=n+1; 
	if(r[ed.y]==0) r[ed.y]=n+1;
	col[c[ed.x]].push_back(ed.y);
	row[r[ed.y]].push_back(ed.x);
	bfs();
	return 0;
}

## STL+BFS做法
[AC历程](https://www.luogu.com.cn/paste/tohvl1cn)
也是AC得很坎坷。

### 思路：
* 使用vector+map记录每一面镜子的坐标。注意：因为每一行每一列可能会有多个镜子，又行列坐标范围太大，我们需要用map离散化。
* 将终点也看作一面镜子加入其中，最后统计答案时-1即可。
* 主要有两项剪枝：

1.如果当前镜子的其中一个坐标与终点的一个坐标相对应，那么将它加入到队头。

2.如果当前行或列的镜子被遍历过，那么跳过，因为肯定加入过队列。

代码如下：

```c++
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef pair<int, int> PII;
const int N=1e6+10;
int n; bool vc[N], vr[N];
unordered_map<int, int> c, r;
vector<int> col[N], row[N];
struct node{int x, y;} st, ed;
struct type{int x, y, op, res;} ;
map<PII, bool> mp[2];
void bfs() {
	int ans=0; 
	deque<type> q;
	q.push_back({st.x, st.y, 0, 0});
	q.push_back({st.x, st.y, 1, 0});
	mp[1][{st.x, st.y}]=True;
	mp[0][{st.x, st.y}]=True;
	while(!q.empty()) {
		auto x=q.front(); q.pop_front();
		if(x.x==ed.x&&x.y==ed.y) {ans=x.res-1; break;}
		if(x.op==0) {
			if(vc[c[x.x]]) continue; vc[c[x.x]]=True;
			for(auto i:col[c[x.x]]) {
				if(!mp[0][make_pair(x.x, i)]) {
					if(i==ed.y) q.push_front({x.x, i, 1, x.res+1});
					else q.push_back({x.x, i, 1, x.res+1});
					mp[0][make_pair(x.x, i)]=True;
				}
			}
		}
		else {
			if(vr[r[x.y]]) continue; vr[r[x.y]]=True;
			for(auto i:row[r[x.y]]) {
				if(!mp[1][make_pair(i, x.y)]) {
					if(i==ed.x) q.push_front({i, x.y, 0, x.res+1});
					else q.push_back({i, x.y, 0, x.res+1});
					mp[1][make_pair(i, x.y)]=True;
				}
			}
		}
	}
	printf("%d\n", ans);
}
int main() {
	scanf("%d", &n);
	scanf("%d%d%d%d", &st.x, &st.y, &ed.x, &ed.y);
	for(int i=1;i<=n;i++) {
		int x, y; scanf("%d%d", &x, &y);
		if(c[x]==0) c[x]=i;  if(r[y]==0) r[y]=i;
		col[c[x]].push_back(y); row[r[y]].push_back(x);
	}
	if(c[ed.x]==0) c[ed.x]=n+1; 
	if(r[ed.y]==0) r[ed.y]=n+1;
	col[c[ed.x]].push_back(ed.y);
	row[r[ed.y]].push_back(ed.x);
	bfs();
	return 0;
}
```