A MST Problem

A MST Problem

时间： 1ms        内存：32M

描述：

It is just a mining spanning tree ( 最小生成树 ) problem, what makes you a little difficult is that you are in a 3D space.

输入：

The first line of the input contains the number of test cases in the file. And t he first line of each case

contains one integer numbers n(0<n<30) specifying the number of the point . The n next n line s, each line

contain s Three Integer Numbers xi,yi and zi, indicating the position of point i.

输出：

For each test case, output a line with the answer, which should accurately rounded to two decimals .

示例输入：

2
2
1 1 0
2 2 0
3
1 2 3
0 0 0
1 1 1

示例输出：

1.41
3.97

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<string.h>
int main()

{

       int n,k;

       scanf("%d",&n);

       for(k=0;k<n;k++)

       {

              char t[2000];
              int a,b,i,j,l;
              int x,y;
              char map[32][33]={0};
              scanf("%d %d", &a,&b);
              scanf("%s", &t);
              l=strlen(t)-1;
              x=31-b;
              y=a;
              for(i=0;i<l;i++)
              {
                     if(t[i]=='E')
                     {
                            map[x+1][y+1]='X';
                            y++;
                     }
                     else if(t[i]=='N')
                     {
                            map[x][y+1]='X';
                            x--;
                     }
                     else if(t[i]=='W')
                     {
                            map[x][y]='X';
                            y--;
                     }
                     else if(t[i]=='S')
                     {
                            map[x+1][y]='X';
                            x++;
                     }
              }
              printf("Bitmap #%d\n",k+1);
              for(i=0;i<32;i++)
              {
                     for(j=1;j<33;j++)
                     {
                            if(map[i][j]!='X')
                                   map[i][j]='.';
                            printf("%c",map[i][j]);
                     }
                     printf("\n");
              }
              printf("\n");
       }
       return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h>
int main()

{

       int n,k;

       scanf("%d",&n);

       for(k=0;k<n;k++)

       {

              char t[2000];
              int a,b,i,j,l;
              int x,y;
              char map[32][33]={0};
              scanf("%d %d", &a,&b);
              scanf("%s", &t);
              l=strlen(t)-1;
              x=31-b;
              y=a;
              for(i=0;i<l;i++)
              {
                     if(t[i]=='E')
                     {
                            map[x+1][y+1]='X';
                            y++;
                     }
                     else if(t[i]=='N')
                     {
                            map[x][y+1]='X';
                            x--;
                     }
                     else if(t[i]=='W')
                     {
                            map[x][y]='X';
                            y--;
                     }
                     else if(t[i]=='S')
                     {
                            map[x+1][y]='X';
                            x++;
                     }
              }
              printf("Bitmap #%d\n",k+1);
              for(i=0;i<32;i++)
              {
                     for(j=1;j<33;j++)
                     {
                            if(map[i][j]!='X')
                                   map[i][j]='.';
                            printf("%c",map[i][j]);
                     }
                     printf("\n");
              }
              printf("\n");
       }
       return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。