Result: Accepted
Time: 3ms
Memory: 1700kB
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
char maze[200][200];
int lastt[200]={0},first[200]={0},lines[200]={0};
int i,j;
int all=0,has=0,res=0,loc=0;
for(i=0;i<n;i++)cin>>maze[i];
maze[0][0]='.';
for(i=0;i<n;i++){
for(j=0;j<m;j++)
if(maze[i][j]=='T'){
first[i]=j;
break; //first tree;
}
for(j=m-1;j>=0;j--)
if(maze[i][j]=='T'){
lastt[i]=j;
break; //last tree;
}
}
for(i=0;i<n;i++) {
for(j=first[i];j<=lastt[i];j++)
if(maze[i][j]=='T')
lines[i]++;
all+=lines[i];
}
int f=0;//0 right 1 left;
for(i=0;i<n-1;i++){
if(has==all)break;
if(!lines[i]){ //some line has no tree
if(abs(loc-first[i+1])<abs(lastt[i+1]-loc)){//left
res+=abs(loc-first[i+1]);
loc=first[i+1];
f=0;
}
else{
res+=abs(lastt[i+1]-loc);
loc=lastt[i+1];
f=1;
}
res++;
continue;
}
if(!f){
f=!f;
res+=lastt[i]-loc,loc=lastt[i];
if(loc<lastt[i+1])res+=lastt[i+1]-loc,loc=lastt[i+1];//walk to last ; f to right;
}
else{
f=!f;
res+=loc-first[i],loc=first[i];
if(loc>first[i+1])res+=loc-first[i+1],loc=first[i+1];
}
has+=lines[i];
if(has==all)break;
res++;
}
// last second
if(has!=all)
if(n%2==0)res+=loc-first[n-1];
else res+=lastt[n-1]-loc;
cout<<res<<endl;
}
}