Submission #1178714

#TimeUsernameProblemLanguageResultExecution timeMemory
1178714prideliqueeePatkice (COCI20_patkice)C++20
50 / 50
0 ms328 KiB
#include<bits/stdc++.h>
using namespace std;
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};
#define f first
#define s second
struct st
{
    int i,j,w;
};
int main()
{
    int n,m;
    cin>>n>>m;
    string s[n];
    int oi,oj;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        for(int j=0;j<m;j++)
        {
            if(s[i][j]=='o')
            {
                oi=i,oj=j;
            }
        }
    }
    queue<st> q;
    char c='O';
    int ans=INT_MAX;
    if(oj+1<m&&(s[oi][oj+1]=='x'))
    {
        cout<<":)\nE";
        return 0;
    }
    if(oi-1>=0&&(s[oi-1][oj]=='x'))
    {
        cout<<":)\nN";
        return 0;
    }
    if(oi+1<n&&(s[oi+1][oj]=='x'))
    {
        cout<<":)\nS";
        return 0;
    }
    if(oj-1>=0&&(s[oi][oj-1]=='x'))
    {
        cout<<":)\nW";
        return 0;
    }
    //int dist[n][m];
    //memset(dist,127,sizeof dist);
    if(oj+1<m&&(s[oi][oj+1]!='.'))
    {
        q.push({oi,oj+1,1});
        //dist[oi][oj+1]=1;
        while(!q.empty())
        {
            auto p=q.front();
            q.pop();
            int i=p.i,j=p.j,w=p.w;
            if(s[i][j]=='x')
            {
                ans=w;
                c='E';
                break;
            }
            if(s[i][j]=='.'||s[i][j]=='o')
            continue;
            if(s[i][j]=='>')
            q.push({i,j+1,w+1});
            else if(s[i][j]=='<')
            q.push({i,j-1,w+1});
            else if(s[i][j]=='^')
            q.push({i-1,j,w+1});
            else
            q.push({i+1,j,w+1});
        }
    }
    
    if(oi-1>=0&&(s[oi-1][oj]!='.'))
    {
        while(!q.empty())
        q.pop();
        q.push({oi-1,oj,1});
        //dist[oi][oj+1]=1;
        while(!q.empty())
        {
            auto p=q.front();
            q.pop();
            int i=p.i,j=p.j,w=p.w;
            if(s[i][j]=='x')
            {
                if(ans>w)
                {
                    ans=w;
                    c='N';
                }
                break;
            }
            if(s[i][j]=='.'||s[i][j]=='o')
            continue;
            if(s[i][j]=='>')
            q.push({i,j+1,w+1});
            else if(s[i][j]=='<')
            q.push({i,j-1,w+1});
            else if(s[i][j]=='^')
            q.push({i-1,j,w+1});
            else
            q.push({i+1,j,w+1});
        }
    }
    
    if(oi+1<n&&(s[oi+1][oj]!='.'))
    {
        while(!q.empty())
        q.pop();
        q.push({oi+1,oj,1});
        //dist[oi][oj+1]=1;
        while(!q.empty())
        {
            auto p=q.front();
            q.pop();
            int i=p.i,j=p.j,w=p.w;
            if(s[i][j]=='x')
            {
                if(ans>w)
                {
                    ans=w;
                    c='S';
                }
                break;
            }
            if(s[i][j]=='.'||s[i][j]=='o')
            continue;
            if(s[i][j]=='>')
            q.push({i,j+1,w+1});
            else if(s[i][j]=='<')
            q.push({i,j-1,w+1});
            else if(s[i][j]=='^')
            q.push({i-1,j,w+1});
            else
            q.push({i+1,j,w+1});
        }
    }
    
    if(oj-1>=0&&(s[oi][oj-1]!='.'))
    {
        while(!q.empty())
        q.pop();
        q.push({oi,oj-1,1});
        //dist[oi][oj+1]=1;
        while(!q.empty())
        {
            auto p=q.front();
            q.pop();
            int i=p.i,j=p.j,w=p.w;
            if(s[i][j]=='x')
            {
                if(ans>w)
                {
                    ans=w;
                    c='W';
                }
                break;
            }
            if(s[i][j]=='.'||s[i][j]=='o')
            continue;
            if(s[i][j]=='>')
            q.push({i,j+1,w+1});
            else if(s[i][j]=='<')
            q.push({i,j-1,w+1});
            else if(s[i][j]=='^')
            q.push({i-1,j,w+1});
            else
            q.push({i+1,j,w+1});
        }
    }
    if(c!='O')
    {
        cout<<":)\n";
        cout<<c;
    }
    else
    cout<<":(";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...