oj.uz

Submission #402252

# Submission time Handle Problem Language Result Execution time Memory
402252 2021-05-11T13:02:20 Z keta_tsimakuridze Patkice (COCI20_patkice) C++14
50 / 50
 1 ms 392 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=105,mod=1e9+7,Inf = 1e15 + 1;
int t,dist[N][N],n,m;
char a[N][N];
queue<pair<int,pair<int,int> > > q;
string s;
bool ok(int x,int y){
	if(min(x,y)<1 || x>n || y>m) return 0;
	return 1;
}
void bfs(){
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) dist[i][j] = Inf;
	
	while(q.size()){
		int d = q.front().f;
		int i=q.front().s.f;
		int j=q.front().s.s;
		q.pop();
		dist[i][j] = d;
		if(a[i][j] == '.' || a[i][j]=='x') continue;
		int dx=0,dy=0;
		if(a[i][j]=='>') dx=0,dy=1;
		else if(a[i][j]=='<') dx=0,dy=-1;
		else if(a[i][j]=='^') dx=-1,dy=0;
		else dx=1,dy=0;  
		if(dist[i+dx][j+dy] > d+1){
			dist[i+dx][j+dy] = d+1;
			q.push({d+1,{i+dx,j+dy}});
		} 
	}
}
 main(){
	// t=1;
	cin >> n >> m;
	int I=0,J=0,I_,J_;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j] == 'o') I=i,J=j;
			else if(a[i][j] =='x') I_=i,J_=j;
		}
	}
	// E N S W
	int ans = Inf,i=I,j=J;
	char ch='a';
	if(ok(i,j+1)) q.push({0,{i,j+1}});
	bfs();
	ans = dist[I_][J_]; ch='E';
	if(ok(i-1,j)) q.push({0,{i-1,j}});
	bfs();
	if(dist[I_][J_]<ans) ans = dist[I_][J_],ch='N';
	if(ok(i+1,j)) q.push({0,{i+1,j}});
	bfs();
	if(dist[I_][J_]<ans) ans = dist[I_][J_],ch='S';
	if(ok(i+1,j-1)) q.push({0,{i,j-1}});
	bfs();	
	if(dist[I_][J_]<ans) ans = dist[I_][J_],ch='W';
	if(ans==Inf)cout<<":("<<endl; else cout<<":)"<<endl,cout<<ch;
}

Compilation message

patkice.cpp:37:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 |  main(){
      |  ^~~~
patkice.cpp: In function 'int main()':
patkice.cpp:53:6: warning: 'J_' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |  ans = dist[I_][J_]; ch='E';
      |  ~~~~^~~~~~~~~~~~~~
patkice.cpp:53:6: warning: 'I_' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 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 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 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 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 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 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 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 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct