2017年上海金马五校程序设计竞赛：Problem K : Treasure Map

比眉伴天荒 2022-06-13 23:49 105阅读 0赞

### Problem K : Treasure Map ###

From: [DHUOJ, 2017060311][DHUOJ_ 2017060311]

Submit (Out of Contest)

Time Limit: 3 s

--------------------

## Description ##

There is a robot, its task is to bury treasures in order on a N × M grids map, and each treasure can be represented by its weight, which is an integer.  
  
The robot begins to bury the treasures from the top-left grid. Because it is stupid, it can only [Go][] straight until the border or the next grid has already been buried a treasure, and then it turns right.  
  
Its task is finished when all treasures are buried. Please output the treasure map as a N × M matrix.

![5j84iKUQiV_agimadei.png][]

## Input ##

There are several test cases, each one contains two lines.  
First line: two integers N and M (1 ≤ N, M ≤ 100), indicate the size of the map.  
Second line: N × M integers, indicate the weight of the treasures in order.

## Output ##

For each test case, output a N × M matrix contains the weight of the treasures buried by the robot. There is one space between two integers.

## Sample Input ##

2 2
    3 2 1 4
    3 3
    1 2 3 4 5 6 7 8 9

## Sample Output ##

3 2
    4 1
    1 2 3
    8 9 4
    7 6 5

题目意思就是给定一个n\*m的数组，然后按照蛇形填数的形式填进去，最后输出即可。。

然后我就按照最简单的蛇形填数来做了，测试数据都过了呀，亲，然后就是超时超时超时~~~~~TLE TLE TLE  0.0

附上超市的代码：

#include <iostream>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    int a[111][111];
    int main()
    {
        int n,m,count,x,y,b[10001];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            for(int i=1; i<=n*m; i++)
            {
                scanf("%d",&b[i]);
            }
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                a[i][j]=0;
            a[x=0][y=0]=b[1];
            count =  1;
            while(count<n*m)
            {
                while(y+1<m &&!a[x][y+1])  a[x][++y] =b[++count];
                while(x-1>=0 &&!a[x-1][y]) a[--x][y]=b[++count];
                while(y-1>=0 &&!a[x][y-1]) a[x][--y]=b[++count];
                while(x+1<n && !a[x+1][y]) a[++x][y]=b[++count];
            }
            for(x=0; x<n; x++)
            {
                for(y=0; y<m; y++)
                {
                    if(y==m-1)
                        printf("%d",a[x][y]);
                    else
                    printf("%d ",a[x][y]);
                }
                printf("\n");
            }
        }
    }

不知道为啥超时呀，感觉基本原理都是这样的。。。。。

然后dalao   AC的代码在此：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    
    const int maxn = 102;
    int N,M;
    int Map[maxn][maxn];
    int a[maxn*maxn];
    int main()
    {
        int up,down,left,right;     ///分别记录上边界，下边界，左边界，右边界
        while(~scanf("%d%d",&N,&M))
        {
            for(int i = 1; i <= N*M; i++)
                scanf("%d",&a[i]);
            up = 0;
            down = N+1;
            left = 0;
            right = M+1;
            int ccount = 1;
            while(1)
            {
                ///先向右填数
                if(up+1<down) ///必须要判断，上下边界相邻，不能填数了。同理左右边界相邻也不能填数了。
                {
                    for(int i = left+1; i<right; i++)
                    {
                        Map[up+1][i] = a[ccount++];
                    }
                    up++;
                }
                else break;
                ///然后往下走
                if(left<right-1)
                {
                    for(int i = up+1; i < down; i++)
                    {
                        Map[i][right-1] = a[ccount++];
                    }
                    right--;
                }
                else break;
                ///然后往左走
                if(up<down-1)
                {
                    for(int i = right-1; i > left; i--)
                    {
                        Map[down-1][i] = a[ccount++];
                    }
                    down--;
                }
                else break;
                ///然后往上走
                if(left+1<right)
                {
                    for(int i = down-1; i > up; i--)
                    {
                        Map[i][left+1] = a[ccount++];
                    }
                    left++;
                }
                else break;
            }
            for(int i = 1; i <= N; i++)
            {
                for(int j = 1; j <= M; j++)
                {
                    if(j == 1) printf("%d",Map[i][j]);
                    else printf(" %d",Map[i][j]);
                }
                printf("\n");
            }
        }
        return 0;
    }

[dalao的博客链接][dalao]

[DHUOJ_ 2017060311]: http://acm.dhu.edu.cn/dhuoj
[Go]: http://lib.csdn.net/base/go
[5j84iKUQiV_agimadei.png]: http://acm.dhu.edu.cn/images/DHUOJ/eoL2E8JEoG/5j84iKUQiV_agimadei.png
[dalao]: http://blog.csdn.net/wyxeainn/article/details/72854160