Maze

ZOJ Problem Set - 3225

---

---

There is a maze that has n entrances in the top while n exits in the other side.

In this maze, Mr Maze can go down, go left, go right but he can’t go up.
What’s more, he have to turn left or right if he could.

Both entrances and exits will be numbered from left to right starting by 1.

Now, Mr Maze is at No.a extrance and he wants to go to No.b exit.
And he has only one chance to go straight when he has to turn.
Of course he can only do this when he could go forward.
Can he get to the exit?

Input

The input contains multiple test cases (no more than 30).
The first line only contains an integer n. (1 <= n <= 1000)
Then follow n-1 lines.
The i+1-th line describes the horizontal lines which begin with the i-th vertical line.
Each line begin with an integer m which means there are m horizontal lines. (1 <= m <= 1000)
Then m integers follow. Each integer describes a horizontal line’s distance from the top.
All the integer will be larger than 0 and less than 100000000.
And there won’t be two horizontal lines having same distance if they begin or end with same vertical lines.
The last line contains two integers a and b. (1 <= a,b <=n)

Output

For each case print Yes if Mr Maze could reach the correct exit.
Print No otherwise.

Sample Input

3
1 1
1 2
1 2
4
1 2
1 1
1 2
1 4

Sample Output

Yes
No

---

说明：每次可以左转或右转时必须左转或右转，但允许总共有一次机会，可以往前直走，而不选择左转或右转。

/**
 Input:
6
3 1 3 9
1 6
2 4 11
2 5 8
3 2 7 10
1 3
Output:
No  
 Input:
6
3 1 3 9
1 6
3 4 7 11
2 5 8
3 2 7 10
3 2
Output:
No   **/

// author: jfo()

////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

vector<int> horizon[1002];
set<pair<int, int> > unreachable;
int n;

bool fn(int dist, int pos, int dest, int straightable)
{
if(unreachable.find(make_pair(pos, dist)) != unreachable.end())
return false;

vector<int>::iterator right = upper_bound(horizon[pos].begin(), horizon[pos].end(), dist);
vector<int>::iterator left = upper_bound(horizon[pos-1].begin(), horizon[pos-1].end(), dist);

int d = 0;
int p = 0;

if(right == horizon[pos].end() && left == horizon[pos-1].end()) {
if(pos == dest)
return true;
unreachable.insert(make_pair(pos, dist));
return false;
}
else if(right == horizon[pos].end()) {
d = left;
p = pos - 1;
}
else if(left == horizon[pos-1].end()) {
d = right;
p = pos + 1;
}
else {
if(left < right) {
d = left;
p = pos - 1;
}
else { // left > right
d = right;
p = pos + 1;
}
}

if(fn(d, p, dest, straightable))
return true;

if(straightable) {
if(fn(d, pos, dest, 0))
return true;
}

unreachable.insert(make_pair(pos, dist));
return false;
}

bool walk(int enter, int exit)
{
return fn(0, enter, exit, 1);
}

int main()
{
int i, j;
while(cin >> n) {
int a, b;
for(i = 1; i < n; i++) {
int m;
cin >> m;
horizon[i].clear();
int t;
for(j = 0; j < m; j++) {
cin >> t;
horizon[i].push_back(t);
}
sort(horizon[i].begin(), horizon[i].end());
}
horizon[0].clear();
horizon[i].clear();
unreachable.clear();
cin >> a >> b;
if(walk(a, b))
cout << "Yes" << endl;
else
cout << "No" << endl;
}

return 0;
}

如果将题目改为，每次左转或右转时都有一次机会可以选择直走，则fn函数应当稍作改动。