#6298. 「CodePlus 2018 3 月赛」华尔兹

题目类型:答案提交 评测方式:Special Judge
上传者: Snakes

题目描述

这是一道奇怪的题目。

与 CodePlus 线上赛不同,在 LibreOJ,这是一道提交答案题

有一个 n×mn\times m 大小的网格,其中有些格点比较特殊,当玩家站在上面的时候会自动移动到相邻四个方向之一,另外一些格点暂时还并不特殊,因为它们的移动方向还未知,如下图:

Challenge

上图中,第一列和最后一行格点的移动方向未知,其他点的移动方向已经确定了,已经在图中用箭头指出其方向。

现在给定一个起点(上图中的绿色方块)和一个终点(上图中的红色方块),你需要给其中一些(而不一定是全部)移动方向未知的格点确定一个方向,使得玩家能从起点移动到终点。

如下图是一个方案,其中蓝色格点标注出了从起点到终点的路径:

Submit

输入格式

对于一个关卡,其对应的输入文件描述如下。

第一行六个空格隔开的整数 n,m,sx,sy,tx,tyn,m,sx,sy,tx,ty,它们的意义分别如下:

  • nnmm 描述地图的大小,它们分别表示地图的行数、列数。

  • sx,sysx,sy 分别表示起点的行、列坐标,即起点为第 sxsx 行第 sysy 列的格点。(行、列的编号均从 11 开始)

  • tx,tytx,ty 分别表示终点的行、列坐标,描述规则同上。

接下来 nn 行每行 mm 个字符,每个字符表示网格对应位置的状态,不同字符的意义如下:

  • w表示向上移动

  • s表示向下移动

  • a表示向左移动

  • d表示向右移动

  • .表示方向未确定

输出格式

对于一个关卡,其对应的输出文件为将其输入文件中 . 替换为 w, a, s, d 中任意一个字符的结果,其余内容与格式不变。

样例

对于「题目描述」中给定的关卡(第一张图片),其对应的文件描述如下:

4 4 1 1 4 4
.aaa
.www
.sss
....

「题目描述」中第二张图片对应的文件描述为:

4 4 1 1 4 4
saaa
swww
dsss
dddw

数据范围与提示

并不需要http://tmp.chenyu0x00.com 上完成挑战,然后也不需要将通关代码提交到 OJ 上,OJ 也不会根据你的通关代码决定你的最终得分。

特别提示,你可以在不与他人交流,不借助他人帮助的情况下使用任何手段完成挑战,但是对平台的攻击将被视为作弊。可惜现在你已经攻击不到当时的那个平台了 :(


来自 CodePlus 2018 3 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/陈宇 命题/陈宇 验题/吕时清,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。