dreamer面具被揭开，谁是winner，谁是loser？ (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

dreamer面具被揭开，谁是winner，谁是loser？ (转载)

dreamer面具被揭开，谁是winner，谁是loser？ (转载)# Joke - 肚皮舞运动

C*Y2010-03-27 07:03

1 楼

2个半小时，要写出能run的code。题目大意是这样：
N个方块（N已知），每个方块的4条边用数字表示，只有数字相同的两条边才能相邻摆
放，。每次输入一个方块（不是一次性全给N个），有且仅有一个位置能摆放这个方块
，方块可以旋转（90，180，270度）。要求打印出拼好的图案（即所有方块的摆放位置
和旋转角度）。
我当时的想法是，用一个矩阵储存方块在图案中的位置和角度，一个链表储存图案的边
缘（逆时针地）。每输入一个方块，就拿它的4条边跟链表中的边逐个比较，找到了就
记下它的位置和角度，还要注意如果方块的边跟图案中超过1条的边相邻的话（直角的
位置），所有邻边必须相同。找到摆放位置后需要从链表中删除一些边和插入一些边。
即使是像我这个简单的思路，写出bug free的code来还是很费劲啊。哎。。
还有更快的算法和数据结构吗？

A*e2010-03-27 07:03

2 楼

【以下文字转载自 Piebridge 讨论区】
发信人: Antoine (看起来瘦，摸起来有肉), 信区: Piebridge
标题: dreamer面具被揭开，谁是winner，谁是loser？
发信站: BBS 未名空间站 (Sat Mar 27 10:33:20 2010, 美东)
发信人: Antoine (看起来瘦，摸起来有肉), 信区: bagua
标题: dreamer面具被揭开，谁是winner，谁是loser？
发信站: BBS 未名空间站 (Sat Mar 27 10:12:55 2010, 美东)
欢迎提名评选
在八卦版跟贴参与评论的有包子奖励

i*e2010-03-27 07:03

3 楼

这题我有做过，请问lz申的是加州的游戏公司吗？
我的方法很简单，实现也比较简单写，比较容易写成bug free。
首先把拼图放在2D array的中间，然后每次加入新的拼图在有可能的四方形地区里进行
搜索。
以下是我写的代码。
#include
using namespace std;
void rotate(char* tile)
{
char first = tile[0];
strcpy(tile, tile + 1);
tile[3] = first;
tile[4] = '\0';
}
const int MAP_SZ = 1024;
char map[MAP_SZ][MAP_SZ];
void printMap(int x1, int y1, int x2, int y2)
{
for (int j = y1; j <= y2; j++)
{
for (int i = x1; i <= x2; i++)
{
cout << map[i][j];

【在 C*Y 的大作中提到】

: 2个半小时，要写出能run的code。题目大意是这样：
: N个方块（N已知），每个方块的4条边用数字表示，只有数字相同的两条边才能相邻摆
: 放，。每次输入一个方块（不是一次性全给N个），有且仅有一个位置能摆放这个方块
: ，方块可以旋转（90，180，270度）。要求打印出拼好的图案（即所有方块的摆放位置
: 和旋转角度）。
: 我当时的想法是，用一个矩阵储存方块在图案中的位置和角度，一个链表储存图案的边
: 缘（逆时针地）。每输入一个方块，就拿它的4条边跟链表中的边逐个比较，找到了就
: 记下它的位置和角度，还要注意如果方块的边跟图案中超过1条的边相邻的话（直角的
: 位置），所有邻边必须相同。找到摆放位置后需要从链表中删除一些边和插入一些边。
: 即使是像我这个简单的思路，写出bug free的code来还是很费劲啊。哎。。

a*d2010-03-27 07:03

4 楼

其实
那第一个说出来的，还是应该表扬一下

【在 A*****e 的大作中提到】

: 【以下文字转载自 Piebridge 讨论区】
: 发信人: Antoine (看起来瘦，摸起来有肉), 信区: Piebridge
: 标题: dreamer面具被揭开，谁是winner，谁是loser？
: 发信站: BBS 未名空间站 (Sat Mar 27 10:33:20 2010, 美东)
: 发信人: Antoine (看起来瘦，摸起来有肉), 信区: bagua
: 标题: dreamer面具被揭开，谁是winner，谁是loser？
: 发信站: BBS 未名空间站 (Sat Mar 27 10:12:55 2010, 美东)
: 欢迎提名评选
: 在八卦版跟贴参与评论的有包子奖励

s*t2010-03-27 07:03

5 楼

这个公司我前一阵申请了，题目也做出来了，可惜人家只招local，唉。。
这个题目就是考察基本的编程逻辑，从题目给的数据规模限制来看，就是要暴力解法。
我记得要求是用PHP写，是不

【在 C*Y 的大作中提到】

C*Y2010-03-27 07:03

6 楼

对，例子用的PHP，不过题目说可以用任何语言写。当时我也是用C++
不过题目没说数据规模有多大，那个只是例子，可能是我想复杂了
刚开始的时候我想边界只有55种，所以可以把图案的边界放在hash里，每次搜索只要O(
1)的时间，一共只要O(N)的时间。到真正写code的时候还是不熟啊，后来觉得可能不够
时间了改成链表好像比较省code，就这么过了3小时。。。刚看到题目的时候还想这东
西居然要2小时啊，结果做起来成这样子。。哎。。

【在 s*********t 的大作中提到】

: 这个公司我前一阵申请了，题目也做出来了，可惜人家只招local，唉。。
: 这个题目就是考察基本的编程逻辑，从题目给的数据规模限制来看，就是要暴力解法。
: 我记得要求是用PHP写，是不