TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7904
  • 题目
  • P7904龙形填数
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 256MB
    问题描述

    蛇形填数是一道经典的入门题,但是鲍亿番有自己的想法,他认为盘着的蛇不是一条好蛇,只有不断前进才能突破自我,变成真龙,因此,相比于将矩阵填数成回型(盘踞的蛇):

    1 2 3
    8 9 4
    7 6 5
    

    鲍亿番更喜欢将矩阵填成"S"型(行走的龙):

    1 2 3
    6 5 4
    7 8 9
    

    现在给你一个 \(n \times n\) 的初始全零的矩阵,请你将其按第二种方法填数,但是这样子太过简单,所以每一次操作鲍亿番会选择一个子矩阵,请你在其子矩阵上进行填数,并在最后输出整个矩阵。

    输入格式

    第一行两个整数 \(n,m (n\leq 2000,m\leq 3000)\) ,表示矩阵的大小和操作次数

    接下来 \(m\) 行,每行输入三个正整数 \(x,y,k\) ,表示在以 \((x,y)\) 为左上角,边长为 \(k\) 的方阵内填数 \((1\leq x,y \leq n,max(x+k-1,y+k-1)\leq n)\)

    输出格式

    输出一个 \(n \times n\) 的矩阵,表示最后的结果

    样例输入

    3 2
    1 1 3
    2 2 2

    样例输出

    1 2 3 
    6 1 2 
    7 4 3

    提示

    update 2021.3.16: nodgd加了一组hack数据,原来的三份AC代码变成TLE了