DoNotTurn.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
#include <iterator>
#include <fstream>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define DEBUG(x)	cout << #x << " = " << x << "\n"
#define endl 		("\n")

#define	ep		1e-9
#define PI		M_PI
#define E 		M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp		make_pair
#define	pb		push_back

#define	all(c)		(c).begin(), (c).end()
#define	tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())		//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here ; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int)b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i >= loop_ends_here; i--)

#define Pf		printf
#define	Sf		scanf

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

/*
#ifdef DEBUG
	#undef DEBUG
#endif
#define DEBUG
*/

class DoNotTurn
{
public:
	int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M);
};

bool isWall[555][555];
bool vis[555][555][2];
enum {horizontal = 0, vertical = 1};

struct Node {
	int x, y, d, dir;
	Node(int xx, int yy, int dd, int _dir) {
		x = xx, y = yy, d = dd, dir = _dir;
	}
	Node(){};
	bool operator < (const Node &ob) const {
		return this->d > ob.d;
	}
};

bool valid(int x, int y, int N) {
	return x >= 0 && x < N && y >= 0 && y < N && isWall[x][y] == false ;
}
int X[] = {1, -1, 0, 0};
int Y[] = {0, 0, -1, 1};

int DoNotTurn::minimumTurns (int _N, int X0, int A, int B, int Y0, int C, int D, int _P, int M) 
{
	int64 P = _P;
	int64 N = _N;
	CL(isWall, 0);
	CL(vis, 0);

	int64 x = X0 % P, y = Y0 % P;
	x = (x + P) % P;
	y = (y + P) % P;

	while(M --> 0) {
		isWall[ (x%N + N )%N][ (y%N + N ) % N ] = true;
		x = (x*A + B) % P;
		y = (y*C + D) % P;
	}
	isWall[0][0] = isWall[N-1][N-1] = false;
/*
	forn(i, N) {
		forn(j, N)
			cout << (isWall[i][j] ? '#' : '.');
		cout << endl;
	}
	cout << endl;
*/	
	priority_queue <Node> pq;
	pq.push(Node(0, 0, 0, horizontal));
	pq.push(Node(0, 0, 0, vertical));

	while(!pq.empty()) {
		Node nd = pq.top();
		pq.pop();

		if(vis[nd.x][nd.y][nd.dir])
			continue;

//		Pf("(%d, %d): %d,   ", nd.x, nd.y, nd.d);
		vis[nd.x][nd.y][nd.dir] = true;

		if(nd.x == N-1 && nd.y == N-1)
			return nd.d ;

		forn(i, 4) {
			int x = nd.x + X[i];
			int y = nd.y + Y[i];

			if(valid(x, y, N) == false ||  isWall[x][y] == true)
				continue;

			if(nd.dir == horizontal && X[i] != 0 && vis[x][y][nd.dir] == false)
				pq.push(Node(x, y, nd.d, nd.dir));
			if(nd.dir == vertical && Y[i] != 0 && vis[x][y][nd.dir] == false)
				pq.push(Node(x, y, nd.d, nd.dir));
			if(nd.dir == horizontal && X[i] == 0 && vis[x][y][vertical] == false)
				pq.push(Node(x, y, nd.d+1, vertical));
			if(nd.dir == vertical && Y[i] == 0 && vis[x][y][horizontal] == false)
				pq.push(Node(x, y, nd.d+1, horizontal));

/*
			if( (nd.dir == horizontal || nd.dir == -1) && X[i] != 0)
				pq.push(Node(x, y, nd.d, horizontal));
			if( (nd.dir == vertical || nd.dir == -1 ) && Y[i] != 0)
				pq.push(Node(x, y, nd.d, vertical));
			if(nd.dir == vertical && X[i] != 0)
				pq.push(Node(x, y, nd.d+1, horizontal));
			if(nd.dir == horizontal && Y[i] != 0)
				pq.push(Node(x, y, nd.d+1, vertical));
*/
		}
	}


	return -1;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, int p0, int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8, bool hasAnswer, int p9) {
	cout << "Test " << testNum << ": [" << p0 << "," << p1 << "," << p2 << "," << p3 << "," << p4 << "," << p5 << "," << p6 << "," << p7 << "," << p8;
	cout << "]" << endl;
	DoNotTurn *obj;
	int answer;
	obj = new DoNotTurn();
	clock_t startTime = clock();
	answer = obj->minimumTurns(p0, p1, p2, p3, p4, p5, p6, p7, p8);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p9 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p9;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	int p0;
	int p1;
	int p2;
	int p3;
	int p4;
	int p5;
	int p6;
	int p7;
	int p8;
	int p9;
	
	{
	// ----- test 0 -----
	p0 = 2;
	p1 = 0;
	p2 = 0;
	p3 = 1;
	p4 = 0;
	p5 = 0;
	p6 = 1;
	p7 = 10;
	p8 = 2;
	p9 = 1;
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	p0 = 3;
	p1 = 0;
	p2 = 1;
	p3 = 1;
	p4 = 1;
	p5 = 1;
	p6 = 0;
	p7 = 3;
	p8 = 3;
	p9 = -1;
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	p0 = 3;
	p1 = 0;
	p2 = 1;
	p3 = 1;
	p4 = 1;
	p5 = 1;
	p6 = 1;
	p7 = 3;
	p8 = 3;
	p9 = 3;
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	p0 = 10;
	p1 = 911111;
	p2 = 845499;
	p3 = 866249;
	p4 = 688029;
	p5 = 742197;
	p6 = 312197;
	p7 = 384409;
	p8 = 40;
	p9 = 12;
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	p0 = 5;
	p1 = 23;
	p2 = 2;
	p3 = 3;
	p4 = 35;
	p5 = 5;
	p6 = 7;
	p7 = 9;
	p8 = 3;
	p9 = 2;
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	p0 = 2;
	p1 = 0;
	p2 = 0;
	p3 = 0;
	p4 = 0;
	p5 = 0;
	p6 = 0;
	p7 = 1;
	p8 = 0;
	p9 = 1;
	all_right = KawigiEdit_RunTest(5, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	{
	// ----- test 6 -----
	p0 = 250;
	p1 = 246173;
	p2 = 151391;
	p3 = 31981;
	p4 = 364571;
	p5 = 352711;
	p6 = 200293;
	p7 = 120431;
	p8 = 4687;
	p9 = 12;
	all_right = KawigiEdit_RunTest(6, p0, p1, p2, p3, p4, p5, p6, p7, p8, true, p9) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// There is a NxN maze where each cell contains either a wall or empty space.  You are currently in the top-left cell at coordinates (0, 0) and your goal is to reach the bottom-right cell at coordinates (N-1, N-1) making as few turns as possible.  You can choose any of the four cardinal directions as your starting direction.  Then, from each cell, you can either move forward one cell in your current direction or turn left or right by 90 degrees.  You can only walk into empty cells, not walls.
// 
// You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:
// X[0] = X0 MOD P 
// X[i] = (X[i-1]*A+B) MOD P (note that X[i-1]*A+B may overflow a 32-bit integer)
// 
// Y[0] = Y0 MOD P 
// Y[i] = (Y[i-1]*C+D) MOD P (note that Y[i-1]*C+D may overflow a 32-bit integer) 
// 
// Cell (x, y) of the maze contains a wall if and only if it is neither the top-left cell nor the bottom-right cell and there exists a value of i between 0 and M-1, inclusive, such that x=X[i] MOD N and y=Y[i] MOD N.  Return the minimum number of turns you must make to reach the bottom-right cell of this maze, or return -1 if it is impossible.
// 
// 
// DEFINITION
// Class:DoNotTurn
// Method:minimumTurns
// Parameters:int, int, int, int, int, int, int, int, int
// Returns:int
// Method signature:int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M)
// 
// 
// NOTES
// -In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0.
// -The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.
// 
// 
// CONSTRAINTS
// -N will be between 2 and 500, inclusive. 
// -M will be between 0 and 1,000,000, inclusive. 
// -X0, Y0, A, B, C and D will each be between 0 and 1,000,000, inclusive.
// -P will be between 1 and 1,000,000, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// 2
// 0
// 0
// 1
// 0
// 0
// 1
// 10
// 2
// 
// Returns: 1
// 
// There are no walls, so you will have to make only one turn.
// 
// 1)
// 3
// 0
// 1
// 1
// 1
// 1
// 0
// 3
// 3
// 
// Returns: -1
// 
// The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):
// 
// .#.
// .#.
// .#.
// 
// The target is unreachable.
// 
// 2)
// 3
// 0
// 1
// 1
// 1
// 1
// 1
// 3
// 3
// 
// Returns: 3
// 
// The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):
// 
// .#.
// ..#
// #..
// 
// There is only one possible path and it requires 3 turns.
// 
// 3)
// 10
// 911111
// 845499
// 866249
// 688029
// 742197
// 312197
// 384409
// 40
// 
// Returns: 12
// 
// The maze and the optimal path in it are given below ('#' denotes a wall, '.' denotes an empty cell, the path is illustrated using 'p' characters):
// 
// pp##..#..#
// #pp..###..
// .#p#.....#
// ##p...#.#.
// .#p.##.#..
// ##p##.#...
// #pp####...
// pp#.#...#.
// p#pppp#...
// ppp##ppppp
// 
// 
// 4)
// 5
// 23
// 2
// 3
// 35
// 5
// 7
// 9
// 3
// 
// Returns: 2
// 
// The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):
// 
// ...#.
// .....
// ...#.
// .....
// ..#..
// 
// 
// 5)
// 2
// 0
// 0
// 0
// 0
// 0
// 0
// 1
// 0
// 
// Returns: 1
// 
// 
// 
// END KAWIGIEDIT TESTING

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!