제출 #465790

#제출 시각아이디문제언어결과실행 시간메모리
465790AnasBenMoussa포탈들 (BOI14_portals)C++14
0 / 100
32 ms48364 KiB
//keep it up #include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef map<ll, ll> mll; typedef vector<ll> vll; typedef vector<pll> vpll; typedef set<ll> sll; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //ordered_set<int> s; //s.insert(1); s.insert(3); //cout << s.order_of_key(2) << endl; // the number of elements in the s less than 2 //cout << *s.find_by_order(0) << endl; // print the 0-th smallest number in s(0-based) #define all(x) begin(x), end(x) #define pb push_back #define doub(k) printf("%.5lf\n", k) // setprecision(5) //auto r = equal_range(array, array+n, x); //cout << r.second-r.first << "\n"; #define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())//returns the index first element not less than x; #define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())//returns the index first element greater than x; #define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll)) #define mine(a) (*min_element((a).begin(), (a).end())) #define maxe(a) (*max_element((a).begin(), (a).end())) #define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin()) #define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin()) #define ms(AR,x) memset(AR,x,sizeof AR); ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);} ll lcm(ll a , ll b){ return (a * b) / gcd(a , b);} const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; const int dr[8] = {1,1,0,-1,-1,-1, 0, 1}, dc[8] = {0,1,1, 1, 0,-1,-1,-1}; void yes(){ cout<<"YES\n"; } void no(){ cout<<"NO\n"; } int cyt;int cye; char grid[1000][1000];pll star,en;int vis[1000][1000]; int dis[10000][10000]; set<pair<int,int>>adj[1000][1000];int x,y; void solve(int n ,int j){ for(int i=0;i<=1000;i++){ if(grid[n][j-i]!='#'&&grid[n][j-i-1]=='#'){ if(grid[n][j-i]=='#'){ continue; } if(n<=0||j-i<=0||n>x||j-i>y){ continue; } adj[n][j-i].insert({n,j}); adj[n][j].insert({n,j-i}); break; } } for(int i=0;i<=1000;i++){ if(grid[n+i][j]!='#'&&grid[n+i+1][j]=='#'){ if(grid[n+i][j]=='#'){ continue; } if(n+i<=0||j<=0||n+i>x||j>y){ continue; } adj[n+i][j].insert({n,j}); adj[n][j].insert({n+i,j}); break; } for(int i=0;i<=10000;i++){ if(grid[n-i][j]=='#'){ continue; } if(grid[n-i][j]!='#'&&grid[n-i-1][j]=='#'){ if(n-i<=0||j<=0||n-i>x||j>y){ continue; } adj[n-i][j].insert({n,j}); adj[n][j].insert({n-i,j}); break; } } for(int i=0;i<=10000;i++){ if(grid[n][j+i]=='#'){ continue; } if(grid[n][j+i]!='#'&&grid[n][j+i+1]=='#'){ if(n<=0||j+i<=0||n>x||j+i>y){ continue; } adj[n][j+i].insert({n,j}); adj[n][j].insert({n,j+i}); break; } } for(int r=0;r<4;r++){ if(n+nx[r]<=0||n+nx[r]>x||j+ny[r]<=0||j+ny[r]>y){ continue; } if(grid[n+nx[r]][j+ny[r]]=='#'){ continue; } adj[n][j].insert({n+nx[r],j+ny[r]}); adj[n+nx[r]][j+ny[r]].insert({n,j}); } }} void bfs(int t,int tt){ queue<pair<int,int>>q; q.push({t,tt}); dis[t][tt]=0; while(!q.empty()){ int r=q.front().first; int c=q.front().second; //cout<<r<<" "<<c<<endl; // cout<<dis[r][c]; q.pop(); for(auto u:adj[r][c]){ if(vis[u.first][u.second]){ continue; } vis[u.first][u.second]=1; dis[u.first][u.second]=dis[r][c]+1; q.push({u.first,u.second}); } } } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>x; cin>>y; memset(grid,'#',sizeof(grid)); for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++){ char t;cin>>t; if(t=='S'){ star={i,j}; } if(t=='C'){ en={i,j}; } grid[i][j]=t; } } for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++){ if(grid[i][j]=='#'){ continue; } solve(i,j); } } /*for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++){ cout<<i<<" "<<j<<"<< "; for(auto u:adj[i][j]){ cout<<u.first<<" "<<u.second<<"["; } cout<<endl; } }*/ bfs(star.first,star.second); // for(int i=1;i<=x;i++){ // for(int j=1;j<=y;j++){ // cout<<i<<" "<<j<<" "<<dis[i][j]<<endl; // } //} cout<<dis[en.first][en.second]; return 0; }
#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...