salt_n_ice's blog

By salt_n_ice, history, 7 weeks ago, In English

Problem Link

Here is my implementation: * Here, sn and en stands for starting node and ending node respectively, and mini_map is the 2d array showing path of shortest distance from starting node to all other reachable nodes. Rest is Breadth-First Search.

I don't see whats making this solution so long

Code
char a[1001][1001];
bool visited[1001][1001];
char mini_map[1001][1001];
bool valid(int i, int j)
{
    if(i>=0 && i<n && j>=0 && j<m && a[i][j]!=-1 && visited[i][j]==false) return true;
    else return false;
}
void solve() {
    cin>>n>>m;
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            char x;
            cin>>x;
            if(x=='.')a[i][j]=0;
            else if(x=='#') a[i][j]=-1;
            else if(x=='A')
            {
                a[i][j]=1;
                sn_i = i;
                sn_j = j;
            }
            else
            {
                a[i][j]=2;
                en_i = i;
                en_j = j;
            }
            visited[i][j]=false;
            mini_map[i][j]='0';
        }
    }
    queue<pair<int, int> > q;
    q.push({sn_i, sn_j});
    while(!q.empty())
    {
        pair<int, int> s = q.front();
        int sf = s.first, ss = s.second;
        q.pop();
        if(valid(sf+1,ss))
        {
            visited[sf+1][ss] = true;
            mini_map[sf+1][ss] = 'D';
            q.push({sf+1,ss});
        }
        if(valid(sf-1,ss))
        {
            visited[sf-1][ss]=true;
            mini_map[sf-1][ss]='U';
            q.push({sf-1,ss});
        }
        if(valid(sf,ss+1))
        {
            visited[sf][ss+1]=true;
            mini_map[sf][ss+1]='R';
            q.push({sf,ss+1});
        }
        if(valid(sf,ss-1))
        {
            visited[sf][ss-1]=true;
            mini_map[sf][ss-1]='L';
            q.push({sf,ss-1});
        }
    }
    int cnt = 0;
    string res = "";
    int i=en_i, j = en_j;
    while(i!=sn_i || j!=sn_j)
    {
        char x = mini_map[i][j];
        if(x=='R') j--;
        else if(x=='L') j++;
        else if(x=='U') i++;
        else if(x=='D') i--;
        else
        {
            cout<<"NO"<<endl;
            return;
        }
        res = res+x;
        cnt++;
    }
    reverse(res.begin(), res.end());
    cout<<"YES"<<endl<<cnt<<endl<<res<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Whenever ask doubt about a problem:

  1. Place your code in spoiler
  2. Insert link to the problem in blog

res = x+res;

this statement works in linear time( every time you insert a new character in front of string all characters of string are shifted one step right)

so insert at back and then reverse the string at the end

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, I will edit the question. And I did 'res = res + x' and still, it's giving me TLE for that case.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A quick google search will show this. There are nice answers with some code snippets.