Submission #1069784

#TimeUsernameProblemLanguageResultExecution timeMemory
1069784vjudge1Toy (CEOI24_toy)C++17
0 / 100
19 ms15616 KiB
// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second #define pii pair<int,int> pii bad = {-1,-1}; int w,h,k,l; int presjek(pii a,pii b) { if (a.ff > b.ff) swap(a,b); if (a.ss < b.ff) return 0; if (b.ss < a.ss) return (b.ss-b.ff+1); return a.ss-b.ff+1; } vector<pii> delta = {{0,1},{1,0},{-1,0},{0,-1}}; pii add(pii a,pii b) { return {a.ff+b.ff,a.ss+b.ss}; } pii sub(pii a,pii b) { return {a.ff-b.ff,a.ss-b.ss}; } void dfs(vector<vector<bool>>& vis,vector<vector<pii>>& rowsegment,vector<vector<pii>>& colsegment,pii cur, pii prev) { if (cur.ff < 0 || cur.ff > h-1 || cur.ss < 0 || cur.ff > w-1 || vis[cur.ff][cur.ss] || colsegment[cur.ff][cur.ss] == bad) return; pii raz = sub(cur,prev); if (abs(raz.ff) < abs(raz.ss)) { if (presjek(colsegment[cur.ff][cur.ss],colsegment[prev.ff][prev.ss]) >= l) { vis[cur.ff][cur.ss] = 1; for (int del = 0; del < 4; del++) { pii cand = add(cur,delta[del]); dfs(vis,rowsegment,colsegment,cand,cur); } } } else if(abs(raz.ff) > abs(raz.ss)) { if (presjek(rowsegment[cur.ff][cur.ss],colsegment[prev.ff][prev.ss]) >= k) { vis[cur.ff][cur.ss] = 1; for (int del = 0; del < 4; del++) { pii cand = add(cur,delta[del]); dfs(vis,rowsegment,colsegment,cand,cur); } } } else { vis[cur.ff][cur.ss] = 1; for (int del = 0; del < 4; del++) { pii cand = add(cur,delta[del]); dfs(vis,rowsegment,colsegment,cand,cur); } } } signed main() { cin >> w >> h >> k >> l; int xh,yh,xv,yv; cin >> xh >> yh >> xv >> yv; vector<vector<int>> grid(h,vector<int>(w,0)); pii win; for (int i = 0; i < h; i++) { string s; cin >> s; for (int j = 0; j < w; j++) { if (s[j] == 'X') grid[i][j] = 1; if (s[j] == '*') win = {i,j}; } } //The rows are numbered from 0 to H − 1 from top to bottom and columns are numbered 0 to //W − 1 from left to right. The x coordinate denotes the column number and y coordinate denotes //the row number vector<vector<pii>> rowsegment(h,vector<pii>(w,bad)); vector<vector<pii>> colsegment(h,vector<pii>(w,bad)); for (int i = 0; i < h; i++) { int prev = 0; for (int j = 0; j < w; j++) { if (!grid[i][j]) rowsegment[i][j].ff = prev; else prev = j+1; } prev = w-1; for (int j = w-1; j >= 0; j--) { if (!grid[i][j]) rowsegment[i][j].ss = prev; else prev = j-1; } } for (int j = 0; j < w; j++) { int prev = 0; for (int i = 0; i < h; i++) { if (!grid[i][j]) colsegment[i][j].ff = prev; else prev = i+1; } prev = h-1; for (int i = h-1; i >= 0; i--) { if (!grid[i][j]) colsegment[i][j].ss = prev; else prev = i-1; } } vector<vector<bool>> vis(h,vector<bool>(w,0)); //vertical part ide po redovima a horizontal po kolonama pii start = {yh,xv}; dfs(vis,rowsegment,colsegment,start,start); /*for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cout << grid[i][j]; } cout << endl; } cout << endl; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cout << "{" << rowsegment[i][j].ff << "," <<rowsegment[i][j].ss << "} "; } cout << endl; } cout << endl; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cout << "{" << colsegment[i][j].ff << "," <<colsegment[i][j].ss << "} "; } cout << endl; } cout << endl; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cout << vis[i][j]; } cout << endl; }*/ if (vis[win.ff][win.ss]) { cout << "YES\n"; } else cout << "NO\n"; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...