Submission #465675

#TimeUsernameProblemLanguageResultExecution timeMemory
465675MohamedAliSaidanePortals (BOI14_portals)C++14
20 / 100
9 ms1332 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; typedef vector<int> vi; typedef long long ll; typedef pair<ll,ll> pll; typedef tuple<int,int,int> ti; typedef unsigned long long ull; typedef long double ld; typedef vector<ll> vll; typedef pair<ld,ld> pld; #define pb push_back #define popb pop_back() #define pf push_front #define popf pop_front #define ff first #define ss second #define MOD (int)(1e9 + 7) #define INF (ll) (1e18) #define all(v) (v).begin(),(v).end() ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} ld pointdist(ld x, ld y, ld point) { return ((x-point)*(y-point))/abs(x-y); } //ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); } const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //East, West, South, North+ ////////////******SOLUTION******\\\\\\\\\\\ const int MAX_R = 1004; char mat[MAX_R][MAX_R]; int r, c; pii start; pii arv; int dist[MAX_R][MAX_R]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> r >> c; for(int i = 0; i <r; i ++) { for(int j = 0; j < c; j ++) { cin >> mat[i][j]; if(mat[i][j] == 'S') start = {i,j}; if(mat[i][j] == 'C') arv = {i, j}; dist[i][j] = MOD; } } set<pair<int,pii>> pq; pq.insert({0,start}); int ans = MOD; while(!pq.empty()) { pair<int,pii> u = *(pq.begin()); pq.erase(pq.begin()); int d = u.ff; pii coord = u.ss; int x = u.ss.ff; int y = u.ss.ss; // cout << x << ' ' << y << '\n' << flush; if(x == arv.ff && y == arv.ss) { cout << d; return 0; } dist[x][y] = d; bool wall = false; for(int i= 0; i < 4; i ++) { int newx = nx[i] + x; int newy = ny[i] + y; if(newx >= 0 && newx < r && newy >= 0 && newy < c && dist[newx][newy] > d + 1 && mat[newx][newy] != '#') { pq.insert({d+1,{newx,newy}}); dist[newx][newy] = d + 1; } if(newx < 0 || newy < 0 || newx == r || newy == y || mat[newx][newy] == '#' ) wall = true; } if(!wall) continue; for(int i = 0; i < 4; i ++) { int a = x; int b = y; while(a >= 0 && b >= 0 && a < r && b < c && mat[a][b] != '#') { a += nx[i]; b += ny[i]; } a -= nx[i]; b -= ny[i]; if(dist[a][b] > d + 1) pq.insert({d+1,{a,b}}); } } //cout << "fin sans res\n"; return 0; } /* Identify problem diagram: Brute force, Greedy, Dynamic Programming, Divide and Conquer Reformulate the problem into something more theoretical !!!!! IMPLICIT GRAPH ?????? !!!!! PAY ATTENTION TO THE CONSTRAINTS: DP nD ? BF ? BITMASKING ? !!!!! SOLVE THE SUBTASKS FIRST: IT'S TOTALLY OK NOT TO SOLVE THE PROBLEM ENTIRELY Search for multiple approaches: select the seemingly optimal one Remember that you're the king of CP Change your approach Imagine Corner cases before submitting Don't spend too much time on the problem: move on ! */

Compilation message (stderr)

portals.cpp:26:1: warning: multi-line comment [-Wcomment]
   26 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^
portals.cpp: In function 'int main()':
portals.cpp:60:13: warning: variable 'coord' set but not used [-Wunused-but-set-variable]
   60 |         pii coord = u.ss;
      |             ^~~~~
portals.cpp:54:9: warning: unused variable 'ans' [-Wunused-variable]
   54 |     int ans = MOD;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...