Start: Dec, 22, 2016 18:15:00
2016年秋季学期程序设计基础第三次考试
End: Dec, 22, 2016 21:00:00
Time elapsed:
Time remaining:

Problem_ID: G
Result: Accepted
Time: 3ms
Memory: 1700kB
Author: mmseasons
In contest: 1080

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