314 - Robot

[Kroppeb]

I don't understand why my code is giving wrong answer, in these input (wich i get on another topic):

Code: Select all

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 south
2 3
0 0 0
0 0 0
1 1 1 2 west
5 5
0 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
1 1 4 4 east
2 3
0 0 0
0 0 1
1 1 1 2 east
0 0

The result was

Code: Select all

12
3
-1
-1

Is this correct?

Is there any special case? Someone have some test cases?

Thanks!

I get these answers too and I get the msg that my answers are wrong.
here is my code:

Code: Select all

// uva314-Robot.cpp : Defines the entry point for the console application.
//#include "stdafx.h"

#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

//init globals
vector< vector< int > > obstakels;
int breedte, hoogte;
set <int> geweest;

bool nietGeweest(pair<int, pair<int, pair<int, int> > > in) {
	if (geweest.count(in.second.second.second + 50 * (in.second.second.first + 50 * in.second.first))) return false;
	geweest.insert(in.second.second.second + 50 * (in.second.second.first + 50 * in.second.first));
	return true;
}

vector< vector <int > > obInit() {
	vector <int> copy(10, 0);
	vector <vector <int> > out(9, copy);
	out[0][6] = 1;
	out[1][8] = 1;
	out[2][3] = 1;
	out[3][2] = 1;
	out[4][6] = 1;
	out[5][5] = 1;
	out[6][4] = 1;
	out[6][3] = 1;
	out[8][0] = 1;
	out[8][8] = 1;
	return out;
}

pair <int, int> richtConv(int richt) {
	pair <int, int> out;
	switch (richt) {
	case 0: out = make_pair(0, -1); break;
	case 1: out = make_pair(1, 0); break;
	case 2: out = make_pair(0, 1); break;
	case 3: out = make_pair(-1, 0); break;
	}
	return out;
}

bool oOB(pair<int, pair<int, pair<int, int> > > in) {
	int h = in.second.second.first;
	int b = in.second.second.second;
	if ((h >= 0) && (b>=0) && (h<hoogte-1) && (b<breedte-1)) {
		return true;
	}
	return false;
}

bool unobstructed(pair<int, pair<int, pair<int, int> > > in) {
	int h = in.second.second.first;
	int b = in.second.second.second;
	if ((obstakels[h][b] == 0) && (obstakels[h + 1][b] == 0) && (obstakels[h][b + 1] == 0) && (obstakels[h + 1][b + 1] == 0)) {
		return true;
	}
	return false;
}

bool allowed(pair<int, pair<int, pair<int, int> > > in) {
	if (oOB(in)) {
		if (unobstructed(in) && nietGeweest(in)) {
//			cout << "   (" << in.second.second.first << ", " << in.second.second.second << ") = a;";
			return true;
		}
	}
//	cout << "   (" << in.second.second.first << ", " << in.second.second.second << ") = da; ";
	return false;
}

int main() {
	std::ios::sync_with_stdio(false);
	// init the variable
	int startB, startH, eindeB, eindeH, richt;
	string richting;
	queue< pair< int, pair< int, pair<int, int> > > > nodes;
	pair<int, pair<int, pair<int, int> > > element;
	pair<int, pair<int, pair<int, int> > > curElement;
	int richtB, richtH;
	pair <int, int> richtBH;
	int b, h;


	// zolang de input niet 0,0 is, do voort
	while (true)
	{
		cin >> hoogte >> breedte;

		// controleer of de input 0,0 is.
		if (hoogte + breedte == 0)
		{
			break;
		}
		obstakels.resize(hoogte);
		// input grondplan
		for (int i = 0; i < hoogte; i++)
		{
			obstakels[i].resize(breedte);
			for (int j = 0; j < breedte; j++)
			{
				cin >> obstakels[i][j];
			}
		}

	//	obstakels = obInit();

		//input start, einde en richting;
		cin >> startH >> startB >> eindeH >> eindeB;
		cin >> richting;

		//convert richting in nummer
		switch (richting[0]) {
		case 'n': richt = 0; break;
		case 'e': richt = 1; break;
		case 's': richt = 2; break;
		case 'w': richt = 3; break;
		}


		//init eerste element
		element = make_pair(0, make_pair(richt, make_pair(startH-1, startB-1)));
		nodes.push(element);
		geweest.insert(element.second.second.second + 50 * (element.second.second.first + 50 * element.second.first));

		while (true) {
			if (nodes.size()) {
				cout << -1 << endl;
				break;
			}
			curElement = nodes.front();
			nodes.pop();
			richtBH = richtConv(curElement.second.first);
			richtB = richtBH.first;
			richtH = richtBH.second;
			h = curElement.second.second.first;
			b = curElement.second.second.second;
		//	cout << endl << "(" << h << "," << b << "), time:" << curElement.first << ", richting:" << curElement.second.first << endl;
			if ((h == eindeH-1) && (b == eindeB-1)) {
				cout << curElement.first << endl;
				break;
			}


			// (0,1,2) = (1,2,3) vooruit; 3=tegen 4 is met
			for (int i = 1; i <= 3; i++)
			{
				element = make_pair(curElement.first + 1, make_pair(curElement.second.first, make_pair(h + richtH*i, b + richtB*i)));

				//out of bounds?
				if (allowed(element)) {
					nodes.push(element);
				}
				else break;
			}
			element = make_pair(curElement.first + 1, make_pair((curElement.second.first + 1) % 4, make_pair(h, b)));
			//out of bounds?
			if (allowed(element)) {
				nodes.push(element);
			}

			element = make_pair(curElement.first + 1, make_pair((curElement.second.first + 3) % 4, make_pair(h, b)));
			//out of bounds?
			if (allowed(element)) {
				nodes.push(element);
			}
		}
		geweest.clear();
	}
	return 0;
}

It's not completely in english but here are some translations.
hoogte (h) => height
breedte (b) =>width
obstakels => obstacles
geweest => have been here
einde => end
richting => direction