Submission #516590

#	Time	Username	Problem	Language	Result	Execution time	Memory
516590		whitedragon	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1859 ms	221664 KiB

tracks

#include<iostream>
#include<vector>
#include<queue>

#define ll long long

using namespace std;

void bfs_0_1(vector<vector<int>>& tab,vector<vector<ll>>& disance,int n,int m)
{
    //dis -1
    deque<pair<int,int>> Q;

    disance[1][1]=0;
    Q.push_back(make_pair(1,1));

    while (!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        Q.pop_front();

        if(i>1)
        {
            if(tab[j][i-1]!=0)
            {
                int val;
                if(tab[j][i]==tab[j][i-1])
                {
                    val=0;
                }
                else
                {
                    val=1;
                }

                if(disance[j][i-1]>disance[j][i]+val || disance[j][i-1]==-1)
                {
                    disance[j][i-1]=disance[j][i]+val;
                    if(val==0)
                    {
                        Q.push_front(make_pair(i-1,j));
                    }
                    else
                    {
                        Q.push_back(make_pair(i-1,j));
                    }
                }

            }
        }

        if(i<n)
        {
            if(tab[j][i+1]!=0)
            {
                int val;
                if(tab[j][i]==tab[j][i+1])
                {
                    val=0;
                }
                else
                {
                    val=1;
                }

                if(disance[j][i+1]>disance[j][i]+val || disance[j][i+1]==-1)
                {
                    disance[j][i+1]=disance[j][i]+val;
                    if(val==0)
                    {
                        Q.push_front(make_pair(i+1,j));
                    }
                    else
                    {
                        Q.push_back(make_pair(i+1,j));
                    }
                }

            }
        }

        if(j>1)
        {
            if(tab[j-1][i]!=0)
            {
                int val;
                if(tab[j][i]==tab[j-1][i])
                {
                    val=0;
                }
                else
                {
                    val=1;
                }

                if(disance[j-1][i]>disance[j][i]+val || disance[j-1][i]==-1)
                {
                    disance[j-1][i]=disance[j][i]+val;
                    if(val==0)
                    {
                        Q.push_front(make_pair(i,j-1));
                    }
                    else
                    {
                        Q.push_back(make_pair(i,j-1));
                    }
                }

            }
        }

        if(j<m)
        {
            if(tab[j+1][i]!=0)
            {
                int val;
                if(tab[j][i]==tab[j+1][i])
                {
                    val=0;
                }
                else
                {
                    val=1;
                }

                if(disance[j+1][i]>disance[j][i]+val || disance[j+1][i]==-1)
                {
                    disance[j+1][i]=disance[j][i]+val;
                    if(val==0)
                    {
                        Q.push_front(make_pair(i,j+1));
                    }
                    else
                    {
                        Q.push_back(make_pair(i,j+1));
                    }
                }

            }
        }
    }
    

}

int main()
{
    int n,m;
    cin>>n>>m;

    vector<int> base(n+1,0);
    vector<vector<int>> tab(m+1,base);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            //tab[j][i]
            char a;
            cin>>a;

            if(a=='R')
            {
                tab[j][i]=1;
            }
            else if (a=='F')
            {
                tab[j][i]=2;
            }
            
        }
    }

    vector<ll> base_1(n+1,-1);
    vector<vector<ll>> distance(m+1,base_1);

    bfs_0_1(tab,distance,n,m);

    ll max_dis=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            //cout<<distance[j][i]<<" ";
            max_dis=max(max_dis,distance[j][i]);
        }
    }

    cout<<max_dis+1<<endl;

    return 0;
}

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