Submission #958666

#	Time	Username	Problem	Language	Result	Execution time	Memory
958666		ramalzaher	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	890 ms	349352 KiB

tracks

/** * * * * * * * * * * * * * **\
 *                             *
 *   Author:Ram Azar Alzaher   *
 * Coded in: YYYY\M\D HH:MM:SS *
 *          Lang: C++          *
 *                             *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define vi vector< int >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define s(i) set< i >
#define us(i) unordered_set< i >
#define set set<int>
#define uset unordered_set<int>
#define mp make_pair
#define f first
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
#define so(x) sort(all(s))
#define so(x) sort(all(s))
#define s second
#define sz size()
#define pb push_back
#define test long long t ;cin >> t ;while(t--)
using namespace std;
//*****************************************************VARIABLES***************************************************************\\\\*******************************\\
//*****************************************************************************************************************************\\\\
//***************************************************************************************************************************************
const double pi=2.0*acos(0.0);
const int inf=1LL<<62LL;
const int mod=1e9+7;
int dx[] {1,-1,0,0};
int dy[] {0,0,1,-1};
int max1 = INT_MIN;
int min1 = INT_MAX;
//*****************************************************************************************************************************\\\\
//**************************************************************************************************************************************
//******************************************************************************************************************************\****************


//*****************************************************FUNCTIONS***************************************************************\\\\*******************************\\
//*****************************************************************************************************************************\\\\
//***************************************************************************************************************************************
void setIO(string name = "")
{
    if(name != "")
    {

        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}
const int N = 4004 ;
int n, m ;
string a[N] ;
int vis[N][N], dis[N][N];
bool isvalid(int x,int y  )
{
    if(x >= n || y >= m || y < 0 || x < 0 )return 0 ;
    if( vis[x][y] ==1 || a[x][y] == '.' )return 0 ;
    return 1 ;
}

//*****************************************************************************************************************************\\\\
//**************************************************************************************************************************************
//******************************************************************************************************************************\****************


signed main()
{
    cin >> n >> m ;
    FOR(i, n )cin >> a[i] ;
    memset(dis , 0 , sizeof dis ) ;
    deque<pii> q ;
    q.push_back({0,0});
    dis[0][0] = 1 ;vis[0][0]= 1;
    int ans = 1  ;
    while(q.sz)
    {
        auto [x, y ] = q.front() ;
        q.pop_front() ;
        FOR(i,  4)
        {
            int nx = dx[i]+x;
            int ny = dy[i]+y;
            if(isvalid(nx, ny ))
            {
                if( a[x][y] == a[nx][ny] )
                {
                    q.push_front({nx, ny });
                    dis[nx][ny] = dis[x][y] ;
                    vis[nx][ny] = 1 ;
                }
                else
                {
                    q.push_back({nx, ny });
                    dis[nx][ny] = dis[x][y] + 1 ;
                    vis[nx][ny] = 1 ;
                }
            }
        }
    }
    ans = dis[n-1][m-1]; 
    cout<< ans << endl ;

    return 0 ;
}
/**
input :


output :
*/

Compilation message (stderr)

tracks.cpp:32: warning: "s" redefined
   32 | #define s second
      | 
tracks.cpp:22: note: this is the location of the previous definition
   22 | #define s(i) set< i >
      | 
tracks.cpp:37:1: warning: multi-line comment [-Wcomment]
   37 | //*****************************************************VARIABLES***************************************************************\\\\*******************************\\
      | ^
tracks.cpp:47:1: warning: multi-line comment [-Wcomment]
   47 | //*****************************************************************************************************************************\\\\
      | ^
tracks.cpp:52:1: warning: multi-line comment [-Wcomment]
   52 | //*****************************************************FUNCTIONS***************************************************************\\\\*******************************\\
      | ^
tracks.cpp:75:1: warning: multi-line comment [-Wcomment]
   75 | //*****************************************************************************************************************************\\\\
      | ^
tracks.cpp: In function 'int main()':
tracks.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |         auto [x, y ] = q.front() ;
      |              ^
tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70