之前在论坛看到一个蚂蚁问题，最近几天没事，做了出来，不知有没有bug,所以请大家没事分析一下（我是业余的，看到rjsp大神的分析感觉算法很重要，我的是笨方法，但是容易理解！
https://bbs.bccn.net/viewthread.php?tid=430731&highlight=%C2%EC%D2%CF%CE%CA%CC%E2原题再贴一遍
=======================================================================================================
一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米/秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。

输入格式：
输入的第一行为数据组数。每组数据的第一行为3个正整数L、T、n（0<=n<=10000）；以下n行每行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。
输出格式：
对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turing表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。

共四个文件，ant.h是主要的数据定义，ant.c是主函数所在，calc.c用于逐步计算，是核心，io.c是控制输入输出的函数！
！！发完四个文件前请不要插楼！！

[ 本帖最后由 Explorerlxz 于 2014-5-31 10:32 编辑 ]

/*======================================
*****************ant.h******************
======================================*/
#define ANT sizeof(struct Ants)
#define GROUP sizeof(struct Groups)
#define INT sizeof(int)
struct Ants
{
  int location;
  char state;
  int number;
  struct Ants *anext;
};
struct Ant
{
    int location;
    char state;
    int last_loc;
    char last_sta;
    int number;
}ant[10000];

struct Groups
{
  int length;
  int time;
  int number;
  struct Ants *anext;
  struct Groups *gnext;
}*head;
int *sum_of_group;

struct Groups是蚂蚁组数结点，struct Ants是输入的蚂蚁结点，struct Ant是按位置从小到大排列的蚂蚁数组

/*==========================================
*********************ant.c********************
============================================*/
#include <stdio.h>
#include <stdlib.h>
#include "ant.h"
#include "io.c"
#include "calc.c"
int main()
{
  head=(struct Groups*)malloc(GROUP);
  sum_of_group=(int *)malloc(INT);
  input(head);
  calc(head);
  output(head);
  return 0;
}

主函数简单，输入，计算，输出，不解释

/*============================================================
********************io.h************************************
/*=========================================================*/

//input
void input(struct Groups *gnext)
{
  int i,j;
  struct Ants *a,*temp;
  struct Groups *g;
  g=gnext;
  scanf("%d",sum_of_group);
  for(i=0;i<*sum_of_group;i++)
  {
    scanf("%d %d %d",&g->length,&g->time,&g->number);
    g->anext=(struct Ants *)malloc(ANT);
    a=g->anext;
    for(j=0;j<g->number;j++)
      {
    scanf("%d %c",&a->location,&a->state);
    a->number=j+1;
    a->anext=(struct Ants *)malloc(ANT);
    a=a->anext;
      }
    temp=a;
    free(temp);
    temp=NULL;    
    g->gnext=(struct Groups *)malloc(GROUP);
    g=g->gnext;
  }
}

/*================================================
*******************output************************
================================================*/
//output
void output(struct Groups *gnext)
{
  int i,j;
  struct Ants *a;
  struct Groups *g;
  g=gnext;
  a=g->anext;
  for(i=0;i<*sum_of_group;i++)
    {
      printf("Case #%d\n",i+1);
      for(j=0;j<g->number;j++)
    {
      switch(a->state)
        {
        case 'L':
          printf("%d L",a->location);break;
        case 'R':
          printf("%d R",a->location);break;
        case 'T':
          printf("%d Turing",a->location);break;
        case 'F':
          printf("Fell off");break;
        default:
          printf("error");
        }
      printf("\n");
      a=a->anext;
    }
      printf("\n");
      g=g->gnext;
      a=g->anext;
    }
}

输入输出也不是很难，就是动态链表，不知能不能叫做二叉树

/*================================================
***************calc.c***************************
================================================*/
#define FELL -1
void move_ant(struct Ant *a,int len,int tim,int num)
{
  int i,j,first,last;
  first=0;
  last=num-1;
  for(;tim>0;tim--)
    {
          j=first;
      if(a[j].last_sta=='L')
        {
          if(tim>a[j].last_loc)
        {
             a[j].state='F';
         a[j].location=FELL;
            }
          else
        a[j].location=a[j].last_loc-tim;
          first++;
        }
        if(a[last].last_sta=='R')
          {
        if(a[last].last_loc+tim>len)
        {
           a[last].state='F';
           a[last].location=FELL;
            }
        else
          a[last].location=a[last].last_loc+tim;
        last--;
          }

      //=====================================================
      
       for(j=first;j<=last;j++)
     {
         if((a[j].state=='R')&&(a[j+1].last_loc-a[j].last_loc>2))
        {
          a[j].location+=1;
        }
      else if((a[j].state=='R')&&(a[j+1].last_loc-a[j].last_loc==2))
        {
          if(a[j+1].state=='L')
        {
          a[j].state='L';
          a[j].location+=1;
          j++;
          a[j].state='R';
          a[j].location-=1;
        }
          else
        a[j].location+=1;
        }
      else if((a[j].state=='R')&&(a[j+1].location-a[j].location==1))
        {
          if(a[j+1].state=='L')
        {
          a[j].state='L';
          j++;
          a[j].state='R';
        }
          else
        a[j].location+=1;
        }
      else if((a[j].state=='R')&&(a[j+1].location==a[j].location))
        {
          a[j].state='L';
          a[j].location--;
          a[j+1].state='R';
        }
      else//a[j].state=='L'
        {
          a[j].location--;
        }
      }
    for(j=first;j<=last;j++)
      {
    a[j].last_loc=a[j].location;
    a[j].last_sta=a[j].state;
      }
    }
}
/*==============================================*/
void calc(struct Groups *gnext)
{
  int i,j,n;
  struct Ant atemp;
  struct Ants *a;
  struct Groups *g;
  g=gnext;
  a=g->anext;
  for(n=0;n<*sum_of_group;n++)
    {
      for(i=0;i<g->number;i++)
    {
      ant[i].location=a->location;
      ant[i].state=a->state;
      ant[i].number=a->number;
      a=a->anext;
    }
      a=g->anext;

      for(i=0;i<g->number-1;i++)
    for(j=0;j<g->number-i-1;j++)
      {
        if(ant[j].location>ant[j+1].location)
          {
        atemp.location=ant[j].location;
        ant[j].location=ant[j+1].location;
        ant[j+1].location=atemp.location;

        atemp.state=ant[j].state;
        ant[j].state=ant[j+1].state;
        ant[j+1].state=atemp.state;
        
        atemp.number=ant[j].number;
        ant[j].number=ant[j+1].number;
        ant[j+1].number=atemp.number;
          }
      }   
    
      //initialize last state 
      for(i=0;i<g->number;i++)
    {
      ant[i].last_loc=ant[i].location;
      ant[i].last_sta=ant[i].state;
    }


      /*=======================================================
    asort data and calculate the result*/
      move_ant(ant,g->length,g->time,g->number);
      for(i=0;i<g->number;i++)
    {
      if((ant[i].location==ant[i+1].location)&&(ant[i].location!=FELL))
        {
          ant[i].state='T';
          i++;
          ant[i].state='T';
        }
    }
  //======================================================

      for(i=0;i<g->number-1;i++)
    for(j=0;j<g->number-i-1;j++)
      {
        if(ant[j].number>ant[j+1].number)
          {
        atemp.location=ant[j].location;
        ant[j].location=ant[j+1].location;
        ant[j+1].location=atemp.location;

        atemp.state=ant[j].state;
        ant[j].state=ant[j+1].state;
        ant[j+1].state=atemp.state;
            atemp.number=ant[j].number;
        ant[j].number=ant[j+1].number;
        ant[j+1].number=atemp.number;
          }
      }
   //copy a group of data
      for(i=0;i<g->number;i++)
    {
      a->location=ant[i].location;
      a->state=ant[i].state;
      a->number=ant[i].number;
      a=a->anext;
    }

      g=g->gnext;
      a=g->anext;
    }
}

计算过程有点复杂，我是一秒一秒的计算的，除了第一个蚂蚁和最后一个，一般每个蚂蚁只用考虑右边相邻的蚂蚁，递归……

反观rjsp大神的做法，当我在一秒一秒的移动数据时，他的程序一步到位，越是简洁的程序越不容易出错！我深感佩服，错在起点最可怕了！

赞一个   

我啥都没看 就看到楼主用的是Emacs

不过Emacs默认滚动条在左边好别扭啊。。