oj.uz

Submission #1011794

# Submission time Handle Problem Language Result Execution time Memory
1011794 2024-07-01T08:38:48 Z enkhochir Patkice (COCI20_patkice) C++14
50 / 50
 1 ms 600 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
string s[105];
int dp[105][105];
int sx, sy, gx, gy;
char ans='.';
int mn=1e12;
int tmp=-1;
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
string dir="NSWE";
void bfs(int x, int y){
	queue<pair<int,int>> q;
	q.push({x,y});
	dp[x][y]=2;
	while(!q.empty()){
		int curx=q.front().first, cury=q.front().second;
		q.pop();
//		if(curx==gx and cury==gy){
//				
//		}
		if(s[curx][cury]=='v'){
			if(!dp[curx+1][cury]){
				q.push({curx+1,cury});
				dp[curx+1][cury]=dp[curx][cury]+1;
			}
		}
		else if(s[curx][cury]=='^'){
			if(!dp[curx-1][cury]){
				q.push({curx-1,cury});
				dp[curx-1][cury]=dp[curx][cury]+1;
			}
		}
		else if(s[curx][cury]=='<'){
			if(!dp[curx][cury-1]){
				q.push({curx,cury-1});
				dp[curx][cury-1]=dp[curx][cury]+1;
			}
		}
		else if(s[curx][cury]=='>'){
			if(!dp[curx][cury+1]){
				q.push({curx,cury+1});
				dp[curx][cury+1]=dp[curx][cury]+1;
			}
		}
		
	}
	if(!dp[gx][gy]) tmp=-1;
	else tmp=dp[gx][gy];
}
signed main(){
	cin>>n>>m;
	for(int i=0; i<n; i++){
		cin>>s[i];
		for(int j=0; j<s[i].size(); j++){
			if(s[i][j]=='o'){
				sx=i, sy=j;
			}
			if(s[i][j]=='x'){
				gx=i, gy=j;	
			}
		}
	}
	for(int i=0; i<4; i++){
		int nx=dx[i]+sx, ny=dy[i]+sy;
		memset(dp,sizeof(dp),0);
		for(int j=0; j<n; j++){
			for(int k=0; k<m; k++){
				dp[j][k]=0;
			}
		}
		dp[sx][sy]=1;
		if(nx>=0 and nx<n and ny>=0 and ny<m){
			dp[nx][ny]=2;
			tmp=-1;
			bfs(nx,ny);
			if(tmp==-1) continue;
			else{
				if(tmp<mn){
					mn=tmp;
					ans=dir[i];	
				}
				else if(tmp==mn){
					if(ans>dir[i]) ans=dir[i];		
				}
			}
		}
	}
	if(ans=='.'){
		cout<<":("<<endl;	
	}
	else{
		cout<<":)"<<endl;
		cout<<ans<<endl;
	}
}

Compilation message

patkice.cpp: In function 'int main()':
patkice.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int j=0; j<s[i].size(); j++){
      |                ~^~~~~~~~~~~~
patkice.cpp:67:25: warning: 'memset' used with constant zero length parameter; this could be due to transposed parameters [-Wmemset-transposed-args]
   67 |   memset(dp,sizeof(dp),0);
      |                         ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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