//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[100][1000];int x,y;
void solve(int n ,int j){
for(int i=0;i<=100;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 time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
6092 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5964 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5964 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
5964 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
