143 lines
3.7 KiB
C++
143 lines
3.7 KiB
C++
#ifndef __PROGTEST__
|
|
#include <algorithm>
|
|
#include <assert.h>
|
|
#include <cassert>
|
|
#include <cctype>
|
|
#include <cstdio>
|
|
#include <cstdlib>
|
|
#include <cstring>
|
|
#include <deque>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
#include <list>
|
|
#include <map>
|
|
#include <memory>
|
|
#include <queue>
|
|
#include <set>
|
|
#include <sstream>
|
|
#include <stack>
|
|
#include <stdexcept>
|
|
#include <string>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
// https://fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-pa2/pa2_zkou%C5%A1ka_2023-06-15
|
|
|
|
class CPos {
|
|
public:
|
|
CPos(int y, int x, int hour)
|
|
: m_hour(hour), m_posY(y), m_posX(x)
|
|
{
|
|
}
|
|
|
|
int m_hour;
|
|
int m_posY;
|
|
int m_posX;
|
|
};
|
|
#endif /* __PROGTEST__ */
|
|
|
|
|
|
|
|
class CBattleRoyale {
|
|
public:
|
|
CBattleRoyale(unsigned height, unsigned width, const std::list<CPos> &zones)
|
|
: _h(height), _w(width) {
|
|
for (const auto i : zones)
|
|
_zones[{i.m_posX, i.m_posY}] = i.m_hour;
|
|
}
|
|
|
|
// des (if needed)
|
|
|
|
unsigned findRoute(int ySt, int xSt, int yEn, int xEn) const {
|
|
if (ySt < 0 ||ySt >= _h ||
|
|
yEn < 0 ||yEn >= _h ||
|
|
xSt < 0 ||xSt >= _w ||
|
|
xEn < 0 ||xEn >= _w)
|
|
throw std::logic_error("");
|
|
auto it = _zones.find({xSt, ySt});
|
|
if (it != _zones.end() && !it->second)
|
|
throw std::logic_error("");
|
|
|
|
std::set< std::pair< int, int > > v;
|
|
std::queue< std::tuple< int, int, int > > q;
|
|
|
|
v.emplace(xSt, ySt);
|
|
q.emplace(xSt, ySt, 0);
|
|
|
|
while (q.size()) {
|
|
auto i = q.front();
|
|
q.pop();
|
|
if (std::get<0>(i) == xEn && std::get<1>(i) == yEn)
|
|
return std::get<2>(i);
|
|
|
|
int x[4] = {1,-1,0,0};
|
|
int y[4] = {0,0,1,-1};
|
|
|
|
for (int j = 0; j < 4; ++j) {
|
|
int newX = std::get<0>(i) + x[j];
|
|
int newY = std::get<1>(i) + y[j];
|
|
if (newX < 0 || newY < 0 || newX >= _w || newY >= _h) continue;
|
|
auto it = _zones.find({newX, newY});
|
|
if (( it == _zones.end() || it->second > std::get<2>(i) + 1) &&
|
|
v.find({newX, newY}) == v.end()) {
|
|
q.emplace(newX, newY, std::get<2>(i) + 1);
|
|
v.emplace(newX, newY);
|
|
}
|
|
}
|
|
}
|
|
throw std::logic_error("");
|
|
|
|
}
|
|
|
|
private:
|
|
int _h, _w;
|
|
std::map< std::pair< int, int >, int > _zones;
|
|
};
|
|
|
|
|
|
|
|
#ifndef __PROGTEST__
|
|
int main() {
|
|
CBattleRoyale r1(5, 5, {});
|
|
assert(r1.findRoute(0, 0, 4, 0) == 4);
|
|
assert(r1.findRoute(4, 4, 4, 4) == 0);
|
|
|
|
CBattleRoyale r2(6, 7, {CPos(1, 0, 1), CPos(2, 1, 2), CPos(3, 2, 5)});
|
|
assert(r2.findRoute(0, 0, 4, 0) == 10);
|
|
|
|
|
|
CBattleRoyale r3(8, 8, {CPos(0, 2, 1), CPos(3, 1, 2), CPos(2, 1, 0)});
|
|
try {
|
|
r3.findRoute(2, 1, 4, 7);
|
|
assert("Exception missing!" == nullptr);
|
|
} catch (const logic_error &e) {
|
|
} catch (...) {
|
|
assert("Invalid exception thrown!" == nullptr);
|
|
}
|
|
assert(r3.findRoute(0,2,3,0)==5);
|
|
|
|
CBattleRoyale b(5,5,{CPos(0,1,1),CPos(1,1,0)});
|
|
assert(b.findRoute(0,0,2,2)==4);
|
|
assert(b.findRoute(0,0,0,2)==6);
|
|
assert(b.findRoute(3,3,3,3)==0);
|
|
try{
|
|
assert(b.findRoute(1,1,2,1)==1);
|
|
assert("Kde vyjimka?"==nullptr);
|
|
} catch (logic_error & x){}
|
|
try{
|
|
assert(b.findRoute(1,1,1,1)==0);
|
|
assert("Kde vyjimka? xd"==nullptr);
|
|
} catch (logic_error & x){}
|
|
|
|
CBattleRoyale b1(5,5,{CPos(2,0,2), CPos(2,1,1),CPos(2,2,1), CPos(2,3,3),CPos(2,4,4)});
|
|
try{
|
|
b1.findRoute(1,1,3,1);
|
|
assert("Kde vyjimka?"==nullptr);
|
|
} catch (logic_error & x){}
|
|
|
|
std::cout << "success!\n";
|
|
}
|
|
#endif /* __PROGTEST__ */ |