| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 991751 |
2024-06-03T05:15:40 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
1 ms |
4556 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(cont) ls.begin(), ls.end()
#define rall(cont) ls.rbegin(), ls.rend()
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 998244353
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
//template <class T>
//using Tree = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;//use to count elements lesser than x in an ordered set and in constant time
// ~-~-~-~-~-~-~-~-~-~ MAIN CODE ~-~-~-~-~-~-~-~-~
char grid[505][505];
ll dist1[505][505];
ll dist2[505][505];
bool visited1[505][505];
bool visited2[505][505];
vector<vector<vector<pl>>>graph;
ll t=1,n,w,h;
bool valid(int x,int y){
return (x>=0 and y>=0 and x<w and y<h and grid[y][x]!='x');
}
pl valid_after(ll x,ll y,ll d){
ll c=0;
ll aa=x,bb=y;
while(true){
c++;
if(c>100){
return {x,y};
}
if(grid[y][x]=='A'){
d+=1;
d%=4;
}
if(grid[y][x]=='C'){
d+=3;
d%=4;
}
if(d==0){
if(!valid(x-1,y)){
return {x,y};
}
else{
x--;
}
}
else if(d==1){
if(!valid(x,y-1)){
return {x,y};
}
else{
y--;
}
}
else if(d==2){
if(!valid(x+1,y)){
return {x,y};
}
else{
x++;
}
}
else if(d==3){
if(!valid(x,y+1)){
return {x,y};
}
else{
y++;
}
}
}
}
void solve(){
cin>>n>>w>>h;
ll x1,x2,y1,y2;
for(int i=0;i<h;i++){
vector<vector<pl>>chh;
for(int j=0;j<w;j++){
vector<pl>cc;
chh.PB(cc);
cin>>grid[i][j];
dist1[i][j]=1e9;
dist2[i][j]=1e9;
if(grid[i][j]=='1'){
x1=j;
y1=i;
dist1[i][j]=0;
visited1[i][j]=1;
}
if(grid[i][j]=='2'){
x2=j;
y2=i;
dist2[i][j]=0;
visited2[i][j]=1;
}
}
graph.PB(chh);
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
for(int k=0;k<4;k++){
pl ch=valid_after(j,i,k);
if(ch.first!=j or ch.second!=i){
graph[i][j].PB(ch);
}
}
}
}
queue<pair<pl,pl>>q;
for(auto i:graph[y1][x1]){
q.push({i,{x1,y1}});
}
while(!q.empty()){
pair<pl,pl>curr=q.front();q.pop();
ll x=curr.first.first,y=curr.first.second,pre_x=curr.second.first,pre_y=curr.second.second;
if(!visited1[y][x]){
dist1[y][x]=min(dist1[y][x],dist1[pre_y][pre_x]+1);
visited1[y][x]=true;
for(auto i:graph[y][x]){
q.push({i,{x, y}});
}
}
}
for(auto i:graph[y2][x2]){
q.push({i,{x2,y2}});
}
while(!q.empty()){
pair<pl,pl>curr=q.front();q.pop();
ll x=curr.first.first,y=curr.first.second,pre_x=curr.second.first,pre_y=curr.second.second;
if(!visited2[y][x]){
dist2[y][x]=min(dist2[y][x],dist2[pre_y][pre_x]+1);
visited2[y][x]=true;
for(auto i:graph[y][x]){
q.push({i,{x, y}});
}
}
}
bool check=0;
ll ans=1e9;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(dist1[i][j]!=1e9 and dist2[i][j]!=1e9){
check=1;
ans=min(ans,dist1[i][j]+dist2[i][j]);
}
}
}
if(check){
cout<<ans;
}
else{
cout<<-1;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// cin>>t;
for(int i=0;i<t;i++){
solve();
}
}
Compilation message
robots.cpp: In function 'std::pair<long long int, long long int> valid_after(long long int, long long int, long long int)':
robots.cpp:34:6: warning: unused variable 'aa' [-Wunused-variable]
34 | ll aa=x,bb=y;
| ^~
robots.cpp:34:11: warning: unused variable 'bb' [-Wunused-variable]
34 | ll aa=x,bb=y;
| ^~
robots.cpp: In function 'void solve()':
robots.cpp:133:22: warning: 'y2' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | for(auto i:graph[y2][x2]){
| ^
robots.cpp:133:26: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | for(auto i:graph[y2][x2]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4556 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4556 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4556 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4556 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
