|
|
back to boardС++ Acc #include <iostream> #include <algorithm> #include <iomanip> #include <utility> #include <vector> #include <string> #include <regex> #include <cmath> #include <set> #include <map> using namespace std; struct Coordinata { int x; int y; }; struct addedCoordinata { int x; int y; double length; }; vector<addedCoordinata> addC; vector<Coordinata> getPoints (int x, int y, const vector<Coordinata>& array) { vector<Coordinata> arr; for (auto dot : array) { if (dot.x <= x && dot.y <= y) { arr.push_back(dot); } } return arr; }; double checkAdded (int x, int y) { for (auto point : addC) { if (point.x == x && point.y == y) return point.length; } return -1; } double solve(int n, int m, const vector<Coordinata>& array) { double check = checkAdded(n, m); if (check != -1) return check; double res = 99999999; for (auto point : getPoints(n, m, array)) { double distance = solve(point.x-1, point.y-1, array) + sqrt(20000.0) + (n - point.x + m - point.y) * 100; if (distance < res) res = distance; } if (res == 99999999) { addedCoordinata koor; koor.x = n; koor.y = m; koor.length = (n + m) * 100; addC.push_back(koor); return koor.length; }; addedCoordinata koor; koor.x = n; koor.y = m; koor.length = res; addC.push_back(koor); return res; } int main() { ios::sync_with_stdio(false); int n, m , k; vector<Coordinata> array; cin >> n >> m >> k; for (int i = 0; i < k; ++i) { int x, y; cin >> x >> y; Coordinata xy{}; xy.x = x; xy.y = y; array.push_back(xy); } cout.setf(ios::fixed,ios::floatfield); cout.precision(0); cout << solve(n, m, array); return 0; } |
|
|