Submission #550875

#	Time	Username	Problem	Language	Result	Execution time	Memory
550875		Bobonbush	Nautilus (BOI19_nautilus)	C++17	66 / 100	1105 ms	237432 KiB

nautilus

#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if(x == -1 || x >y)
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */

int n , m , k;

char a[501][501];
string s;

struct TrangThai
{
    int i , j , kay;
    TrangThai()
    {

    }
    TrangThai(int _i , int _j , int _kay)
    {
        i = _i;
        j = _j;
        kay = _kay;
    }
};
map<char , pair<int ,int >>diction;
map<pair<pair<int ,int > , int > , bool>dict;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , -1 , 1};
int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    diction['W'] = make_pair(0 , -1);
    diction['S'] = make_pair(1 , 0);
    diction['E'] = make_pair(0 , 1);
    diction['N'] = make_pair(-1 , 0);
    cin >> n >> m >> k;
    for(int i =1 ; i <= n ; i++ )
    {
        for(int j =1; j <= m ; j++)
        {
            cin >> a[i][j];
        }
    }
    cin >> s;
    queue<TrangThai>q;
    for(int i = 1; i <= n ; i ++)
    {
        for(int j = 1; j <= m ; j++)
        {
            if(a[i][j] =='.')
            {
                q.push(TrangThai(i , j , 0));
                dict[make_pair(make_pair(i , j) , 0 )] = true;
            }
        }
    }
    int res = 0;
    while(!q.empty())
    {
        TrangThai _trangthai = q.front();
        q.pop();
        int i = _trangthai.i;
        int j = _trangthai.j;
        int kay = _trangthai.kay;
        if(kay == (int)s.size() + 1)
        {
            res++;
            continue;
        }
        if(s[kay] != '?')
        {
            int x = i + diction[s[kay]].first;
            int y = j + diction[s[kay]].second;
            if(x < 1 || x > n ||  y < 1 || y > m)
            {
                continue;
            }
            if(a[x][y] =='#' || dict[make_pair( make_pair(x , y), kay + 1)])
            {
                continue;
            }
            dict[make_pair( make_pair(x , y), kay + 1)] = true;
            q.push(TrangThai(x , y , kay + 1));
            continue;
        }

        for(int z = 0 ; z < 4 ; z++)
        {
            int x = i + dx[z];
            int y = j + dy[z];
            if(x < 1 || x > n ||  y < 1 || y > m)
            {
                continue;
            }
            if(a[x][y] =='#' || dict[make_pair( make_pair(x , y), kay + 1)])
            {
                continue;
            }
            dict[make_pair( make_pair(x , y), kay + 1)] = true;
            q.push(TrangThai(x , y , kay + 1));
        }


    }

    cout << res;

    return 0;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34