Codeforces383 B. Volcanoes（难题，大矩形能否走到终点）

本文主要是介绍Codeforces383 B. Volcanoes（难题，大矩形能否走到终点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Iahub got lost in a very big desert. The desert can be represented as a n × n square matrix, where each cell is a zone of the desert. The cell (i, j) represents the cell at row i and column j (1 ≤ i, j ≤ n). Iahub can go from one cell (i, j) only down or right, that is to cells (i + 1, j) or (i, j + 1).

Also, there are m cells that are occupied by volcanoes, which Iahub cannot enter.

Iahub is initially at cell (1, 1) and he needs to travel to cell (n, n). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (n, n).

Input
The first line contains two integers n (1 ≤ n ≤ 109) and m (1 ≤ m ≤ 105). Each of the next m lines contains a pair of integers, x and y (1 ≤ x, y ≤ n), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to n from top to bottom, and matrix columns are numbered from 1 to n from left to right. There is no volcano in cell (1, 1). No two volcanoes occupy the same location.

Output
Print one integer, the minimum time in which Iahub can arrive at cell (n, n). If no solution exists (there is no path to the final cell), print -1.

Examples
inputCopy
4 2
1 3
1 4
outputCopy
6
inputCopy
7 8
1 6
2 6
3 5
3 6
4 3
5 1
5 2
5 3
outputCopy
12
inputCopy
2 2
1 2
2 1
outputCopy
-1
Note
Consider the first sample. A possible road is: (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4).

参考博客1
参考博客2
很难的一道题┭┮﹏┭┮，感谢大佬题解

题意：
1e9*1e9的矩阵，至多1e5个坏点，只能向右向下走，求起点走到终点的最小步数。

思路：
步数肯定是确定的，关键就是能否走到。
肯定是不能直接bfs看能否从起点遍历到终点的，但是坏点数量不大，肯定是要从坏点着手。

直观的方法是将每一列可以到达的区间求出来，然后看最后一列的可行区间是否包含终点。这个方法就是纯模拟区间合并了，对应解法2。

还有一种方法是bfs。可以想到真正影响结果的只有连上边界的坏点，不与连上边界点关联的点，肯定可以直接绕过去。

我们将x=1或者y=n的点放入队列，然后每次将这个点左下(x+1,y-1)的点上面遇到的第一个坏点和右边遇到第一个坏点入队列，如果最后遇到x=n的坏点或者y=1的坏点，那么就走不到终点。

这样队列中每个点(x,y)，实际表示了左下角为(x,y)，右上角为(1,n)的矩形为不可达矩形（到达了这个部分就出不去了）。从这个矩形下面一行找到往右第一个坏点，左边一列找到往上第一个坏点。相当在这个不可达矩形的基础上，找到周围的坏点，逐步扩大不可达的范围。

当得到x=n的点时，不可达矩形包括了终点。当得到y=1的点是，不可达矩形包括了起点。

这个过程可以用map模拟（这个写法是从参考博客2的博主那里学到的）。

解法1

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;map<int,map<int,int> >mp1,mp2;
int vis[maxn];struct Node {int x,y;
}a[maxn];int main() {int n,m;scanf("%d%d",&n,&m);queue<int>q;for(int i = 1;i <= m;i++) {scanf("%d%d",&a[i].x,&a[i].y);if(a[i].x == 1 || a[i].y == n) {vis[i] = 1;q.push(i);}mp1[a[i].x][a[i].y] = i;mp2[a[i].y][-a[i].x] = i;}while(!q.empty()) {int now = q.front();q.pop();int x = a[now].x,y = a[now].y;if(x == n || y == 1) {printf("-1\n");return 0;}if(mp1.count(x + 1)) {auto it = mp1[x + 1].lower_bound(y - 1);if(it != mp1[x + 1].end() && !vis[it -> second]) {q.push(it -> second);vis[it -> second] = 1;}}if(mp2.count(y - 1)) {auto it = mp2[y - 1].lower_bound(-(x + 1));if(it != mp2[y - 1].end() && !vis[it -> second]) {q.push(it -> second);vis[it -> second] = 1;}}}printf("%d\n",2 * n - 2);return 0;
}

解法2

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 2e5 + 7;struct Node {int x,y;
}las[maxn],cur[maxn],a[maxn];//上一列的可行区间，当前这一列的可行区间，坏点。
int n,m;int cmp(Node a,Node b) {if(a.y == b.y) return a.x < b.x;return a.y < b.y;
}bool judge() {int cnt = 1;las[0].x = 1;las[0].y = 1;for(int i = 1;i <= m;i++) {if(a[i].y > a[i - 1].y + 1) { //有几列空行，那么区间上界不变，下界变成n。cnt = 1;las[0].y = n;}int k = 0,pre = 0,num = 0;for(k = i + 1;k <= m && a[k].y == a[i].y;k++) {}k--;for(int j = i;j <= k;j++) {if(a[j].x > pre + 1) {cur[num++] = {pre + 1,a[j].x - 1};}pre = a[j].x;}if(n > pre) {cur[num++] = {pre + 1,n};}int t = 0;for(int j = 0;j < cnt;j++) {while(cur[t].x <= las[j].y && t < num) {if(cur[t].y >= las[j].x) {cur[t].x = max(cur[t].x,las[j].x);} else {cur[t].x = cur[t].y = -1;}t++;}if(t >= num) break;}cnt = 0;for(int j = 0;j < t;j++) {if(cur[j].x == -1) continue;las[cnt++] = {cur[j].x,cur[j].y};}if(cnt == 0) {return false;}i = k;}if(a[m].y != n) return true;if(las[cnt - 1].y == n) return true;return false;
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++) {scanf("%d%d",&a[i].x,&a[i].y);}sort(a + 1,a + 1 + m,cmp);if(judge()) printf("%d\n",2 * n - 2);else printf("-1\n");return 0;
}