oj.uz

Submission #447675

# Submission time Handle Problem Language Result Execution time Memory
447675 2021-07-27T10:07:08 Z Apiram Patkice (COCI20_patkice) C++14
50 / 50
 1 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;
int ans =INT_MAX;
struct points {
	int x,y,cnts;
	char c;
};
vector<string>arr(200);
points add(points startt,int i,int j,int k,char b){
	points a;
	a.x=startt.x+i;
	a.y=startt.y+j;
	a.cnts=startt.cnts+k;
	a.c =b;
	return a;
}
bool check(points u,int n,int m){
	if (u.x<0||u.y<0)return false;
	if (u.x>=n||u.y>=m)return false;
	if (arr[u.x][u.y]=='.')return false;
	if (u.cnts>ans)return false;
	return true;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
points startt,endd;
for (int i = 0; i<n;++i){
	cin>>arr[i];
	for (int j = 0;j<m;++j){
		if (arr[i][j]=='x'){
			endd.x=i;
			endd.y=j;
			endd.cnts=0;
		}
		else if(arr[i][j]=='o'){
			startt.x=i;
			startt.y=j;
			startt.cnts=0;
		}
	}
}
queue<points>q;
q.push(add(startt,0,1,1,'E'));
q.push(add(startt,1,0,1,'S'));
q.push(add(startt,0,-1,1,'W'));
q.push(add(startt,-1,0,1,'N'));
vector<vector<int>>dist(n,vector<int>(m,INT_MAX));
dist[startt.x][startt.y]=0;
vector<pair<int,char>>answer;
while(!q.empty()){
	points u = q.front();
	q.pop();
	if (!check(u,n,m))continue;
	if (arr[u.x][u.y]=='x'){
		ans=min(ans,u.cnts);
		answer.push_back({u.cnts,u.c});
		continue;
	}
	if (dist[u.x][u.y]<u.cnts)continue;
	dist[u.x][u.y]=u.cnts;
	if (arr[u.x][u.y]=='>'){
		q.push(add(u,0,1,1,u.c));
	}
	else if (arr[u.x][u.y]=='<'){
		q.push(add(u,0,-1,1,u.c));
	}
	else if (arr[u.x][u.y]=='^'){
		q.push(add(u,-1,0,1,u.c));
	}
	else{
		q.push(add(u,1,0,1,u.c));
	}
	
}
sort(answer.begin(),answer.end());
if (ans!=INT_MAX){
	cout<<":)\n";
	cout<<answer[0].second<<endl;
}
else{
	cout<<":(\n";
}


return 0;}

Compilation message

patkice.cpp: In function 'int main()':
patkice.cpp:28:15: warning: variable 'endd' set but not used [-Wunused-but-set-variable]
   28 | points startt,endd;
      |               ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 248 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct