### salt_n_ice's blog

By salt_n_ice, history, 2 months ago,

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;
}


• -18

 » 2 months ago, # | ← Rev. 2 →   0 Whenever ask doubt about a problem: Place your code in spoiler 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
•  » » 2 months ago, # ^ |   0 Okay, I will edit the question. And I did 'res = res + x' and still, it's giving me TLE for that case.
•  » » » 2 months ago, # ^ |   0 use fast_io
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 res = res + x works in linear time as well. Try res.push_back(x).
•  » » » 2 months ago, # ^ |   0 a = a + b is done in $O(|a| + |b|)$. a += b is done in $O(|b|)$
 » 2 months ago, # |   0 A quick google search will show this. There are nice answers with some code snippets.