Advertisement
steverobinson

Ant tunnel [New Working]

Oct 15th, 2010
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. class colonysets
  6. {
  7.     public:
  8.         struct coordinates
  9.         {
  10.             int x,y;
  11.             int index;
  12.         };
  13.  
  14.         class adjacency
  15.         {
  16.            public:
  17.             float distance;
  18.             bool traversed;
  19.         };
  20.         coordinates colonies[10];               //Max Number of Colonies would be 10 according to Question
  21.         float length[10];
  22.         int path[10];
  23.         adjacency adjMat[10][10];
  24.         int correctPath[10];
  25.         float leastLength;
  26.         int n;
  27.  
  28.         colonysets(int tn)                      //Constructor
  29.         {
  30.             n=tn;
  31.             for(int i=0;i<n;i++)
  32.                 length[i]=0;
  33.  
  34. /****Receiving Inputs*****/
  35.  
  36.             for(int i=0;i<n;i++)
  37.             {
  38.                 cin>>colonies[i].x;
  39.                 cin>>colonies[i].y;
  40.                 colonies[i].index=i;
  41.             }
  42.  
  43. /*****ADjacency Matrix Initialization*****/
  44.  
  45.             for(int i=0;i<n;i++)
  46.                 for(int j=0;j<n;j++)
  47.                 {
  48.                     if(i==j)
  49.                         adjMat[i][j].distance=0;
  50.                     else
  51.                     {
  52.                         float distance;
  53.                         float temp;
  54.                         temp=((colonies[i].x-colonies[j].x)*(colonies[i].x-colonies[j].x))+((colonies[i].y-colonies[j].y)*(colonies[i].y-colonies[j].y));
  55.                         distance=sqrt(temp);
  56.                         adjMat[i][j].distance=distance;
  57.                     }
  58.                 }
  59.  
  60.  
  61. /** ADJ MAT PRINT
  62.                 for(int i=0; i<n;i++)
  63.                 {
  64.                     cout<<endl;
  65.                     for(int j=0;j<n;j++)
  66.                     cout<<"\t"<<adjMat[i][j].distance;
  67.                 }
  68. **/
  69.  
  70. /*****Distance Calculation For all possible Paths****/
  71.  
  72.             for(int i=0;i<n;i++)
  73.             {
  74.                 for(int l=0;l<n;l++)
  75.                     for(int m=0;m<n;m++)
  76.                     {
  77.                         path[l]=-1;
  78.                         adjMat[l][m].traversed=false;
  79.                     }
  80.  
  81.                for(int d=0;d<n;d++)
  82.                     adjMat[d][i].traversed=true;
  83.  
  84.                 path[0]=i;
  85.                 int k=1;
  86.                 int count=0;
  87.                 for(int j=path[0];count<n;j=path[k-1],count++)
  88.                 {
  89.  
  90.            /***    cout<<"\nHI "<<j;   ***/
  91.  
  92.                     float templength=32767;
  93.                     for(int c=0;c<n;c++)
  94.                     {
  95.                         if((adjMat[j][c].traversed==false)&&(adjMat[j][c].distance<templength)&&(adjMat[j][c].distance!=0))
  96.                         {
  97.                             templength=adjMat[j][c].distance;
  98.                             path[k]=c;
  99.                         }
  100.                     }
  101.                     //cout<<"\nHI"<<path[k];
  102.                     //cout<<endl<<path[k-1];
  103.                     if(templength!=32767)
  104.                         for(int a=0;a<n;a++)
  105.                             adjMat[a][path[k]].traversed=true;
  106.  
  107.                     k++;
  108.                     if(templength!=32767)
  109.                         length[i]+=templength;
  110.  
  111.                 }
  112.                // cout<<endl<<length[i];
  113.             }
  114.  
  115.     /*****Least Distance Calculation *****/
  116.  
  117.             for(int i=0;i<n-1;i++)
  118.                 for(int j=i+1;j<n;j++)
  119.                     if(length[i]>length[j])
  120.                      {
  121.                            float temp=length[i];
  122.                            length[i]=length[j];
  123.                            length[j]=temp;
  124.                       }
  125.             leastLength=length[0];
  126.  
  127. /*****Detection of Path with Least Distance*****/
  128.  
  129.             for(int i=0;i<n;i++)
  130.                 length[i]=0;
  131.             for(int i=0;i<n;i++)
  132.             {
  133.                 for(int l=0;l<n;l++)
  134.                     for(int m=0;m<n;m++)
  135.                     {
  136.                         path[l]=-1;
  137.                         adjMat[l][m].traversed=false;
  138.                     }
  139.  
  140.                for(int d=0;d<n;d++)
  141.                     adjMat[d][i].traversed=true;
  142.  
  143.                 path[0]=i;
  144.                 int k=1;
  145.                 int count=0;
  146.                 for(int j=path[0];count<n;j=path[k-1],count++)
  147.                 {
  148.  
  149.                     float templength=32767;
  150.                     for(int c=0;c<n;c++)
  151.                     {
  152.                         if((adjMat[j][c].traversed==false)&&(adjMat[j][c].distance<templength)&&(adjMat[j][c].distance!=0))
  153.                         {
  154.                             templength=adjMat[j][c].distance;
  155.                             path[k]=c;
  156.                         }
  157.                     }
  158.                     if(templength!=32767)
  159.                         for(int a=0;a<n;a++)
  160.                             adjMat[a][path[k]].traversed=true;
  161.                     k++;
  162.                     if(templength!=32767)
  163.                         length[i]+=templength;
  164.  
  165.                 }
  166.                 if(length[i]==leastLength)
  167.                     {
  168.                         for(int y=0;y<n;y++)
  169.                             correctPath[y]=path[y];
  170.                         goto terminate;
  171.                     }
  172.             }
  173.             terminate:
  174.             int dummy=10;
  175.             dummy++;
  176.         }
  177.  
  178.     //Distance Calculator
  179.     float distance_calc(int x1,int y1,int x2,int y2)
  180.     {
  181.         float distance;
  182.         float temp;
  183.         temp=((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2));
  184.         distance=sqrt(temp);
  185.         return distance;
  186.     }
  187.  
  188.  
  189.     void output()
  190.     {
  191.         /*for(int i=0;i<n;i++)
  192.             cout<<"\n=>"<<correctPath[i]; */
  193.         for(int i=0;i<n-1;i++)
  194.         {
  195.  
  196.             cout<<"\nTUNNEL FROM ("<<colonies[correctPath[i]].x<<","<<colonies[correctPath[i]].y<<") TO ("<<colonies[correctPath[i+1]].x<<","<<colonies[correctPath[i+1]].y<<") is ";
  197.             cout.precision(2);
  198.             cout.setf(ios::fixed,ios::floatfield);
  199.             cout<<distance_calc(colonies[correctPath[i]].x,colonies[correctPath[i]].y,colonies[correctPath[i+1]].x,colonies[correctPath[i+1]].y)<<" m";
  200.         }
  201.         cout<<"\nTOTAL LENGTH OF TUNNEL is "<<leastLength<<" m";
  202.  
  203.     }
  204.  
  205.     colonysets(){}
  206.  
  207.  
  208.  
  209. };
  210.  
  211.  
  212.  
  213. int main()
  214. {
  215.     colonysets colonyset[500]; //Assuming Number of Data Sets Would be <500. Hope so!
  216.  
  217.     int setcount=0;
  218.     int n;
  219.     cin>>n;
  220.     while(n!=0)
  221.     {
  222.         colonyset[setcount]=colonysets(n);
  223.         setcount++;
  224.         cin>>n;
  225.     }
  226.     cout<<"OUTPUT IS";
  227.     for(int i=0;i<setcount;i++)
  228.     {
  229.         cout<<"\nSET "<<i+1;
  230.         colonyset[i].output();
  231.     }
  232.    // system("PAUSE");
  233.     return 0;
  234. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement