Submission #1234594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234594		darshitmittal777	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	832 ms	64416 KiB

tracks

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

// void solve(vector<vector<char>> &grid,char cur,int x, int y)
// {
//     if(x>=grid.size()||x<0||y>=grid[0].size()||y<0)
//     return;
//     if(grid[x][y]!=cur)
//     return;   
//     grid[x][y] = (grid[x][y]=='F')?'R':'F';
//     solve(grid,cur,x,y+1);
//     solve(grid,cur,x,y-1);
//     solve(grid,cur,x+1,y);
//     solve(grid,cur,x-1,y);
// }

int single(vector<vector<char>> &grid)
{
    int c1 = 0,c2=0;
    for(int i=0;i<grid.size();i++)
    {
        for(int j=0;j<grid[0].size();j++)
        {
            if(grid[i][j]=='F')
            c1++;
            else if(grid[i][j]=='R')
            c2++;
        }
    }
    if(c1==0&&c2==0)
    return -1;
    else if(c1==0||c2==0)
    return 1;
    else 
    return 0;
}

// int main()
// {
//     int h,w;cin>>h>>w;
//     vector<vector<char>> grid(h,vector<char>(w));
//     for(int i=0;i<h;i++)
//     {
//         for(int j=0;j<w;j++)
//         {
//             cin>>grid[i][j];
//         }
//     }
//     if(single(grid)==-1)
//     {
//         cout<<0<<endl;
//         return 0;
//     }
//     int ans = 1;
//     while(single(grid)==0)
//     {
//         solve(grid,grid[0][0],0,0);
//         ans++;
//     }
//     cout<<ans<<endl;
//     return 0;
// }


int main()
{
    int h,w;cin>>h>>w;
    vector<vector<char>> grid(h,vector<char>(w));
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>grid[i][j];
        }
    }
    if(single(grid)==-1)
    {
        cout<<0;return 0;
    }
    deque<pair<int,int>>current;
    current.push_back({0,0});
    vector<vector<bool>> vis(h,vector<bool>(w));
    vis[0][0] = true;
    char curr = grid[0][0];
    int ans = 1;
    while(current.size())
    {
        pair<int,int> cur = current.front();
        current.pop_front();
        int x = cur.first, y = cur.second;
        if(grid[x][y]!=curr)
        {
            curr = grid[x][y];
            ans++;
        }
        // right
        if (y + 1 < w && !vis[x][y + 1] && grid[x][y + 1] != '.') {
            vis[x][y + 1] = true;
            if (grid[x][y] == grid[x][y + 1])
                current.push_front({x, y + 1});
            else
                current.push_back({x, y + 1});
        }

        // down
        if (x + 1 < h && !vis[x + 1][y] && grid[x + 1][y] != '.') {
            vis[x + 1][y] = true;
            if (grid[x][y] == grid[x + 1][y])
                current.push_front({x + 1, y});
            else
                current.push_back({x + 1, y});
        }

        // left
        if (y - 1 >= 0 && !vis[x][y - 1] && grid[x][y - 1] != '.') {
            vis[x][y - 1] = true;
            if (grid[x][y] == grid[x][y - 1])
                current.push_front({x, y - 1});
            else
                current.push_back({x, y - 1});
        }

        // up
        if (x - 1 >= 0 && !vis[x - 1][y] && grid[x - 1][y] != '.') {
            vis[x - 1][y] = true;
            if (grid[x][y] == grid[x - 1][y])
                current.push_front({x - 1, y});
            else
                current.push_back({x - 1, y});
        }
    } 
    cout<<ans<<endl;
    return 0;
}

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