C*Y
发帖数: 736 | 1 2个半小时，要写出能run的code。题目大意是这样：
N个方块（N已知），每个方块的4条边用数字表示，只有数字相同的两条边才能相邻摆
放，。每次输入一个方块（不是一次性全给N个），有且仅有一个位置能摆放这个方块
，方块可以旋转（90，180，270度）。要求打印出拼好的图案（即所有方块的摆放位置
和旋转角度）。
我当时的想法是，用一个矩阵储存方块在图案中的位置和角度，一个链表储存图案的边
缘（逆时针地）。每输入一个方块，就拿它的4条边跟链表中的边逐个比较，找到了就
记下它的位置和角度，还要注意如果方块的边跟图案中超过1条的边相邻的话（直角的
位置），所有邻边必须相同。找到摆放位置后需要从链表中删除一些边和插入一些边。
即使是像我这个简单的思路，写出bug free的code来还是很费劲啊。哎。。
还有更快的算法和数据结构吗？ |
i**********e
发帖数: 1145 | 2 这题我有做过，请问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来还是很费劲啊。哎。。
|
s*********t
发帖数: 1663 | 3 这个公司我前一阵申请了，题目也做出来了，可惜人家只招local，唉。。
这个题目就是考察基本的编程逻辑，从题目给的数据规模限制来看，就是要暴力解法。
我记得要求是用PHP写，是不
【在 C*Y 的大作中提到】
: 2个半小时，要写出能run的code。题目大意是这样：
: N个方块（N已知），每个方块的4条边用数字表示，只有数字相同的两条边才能相邻摆
: 放，。每次输入一个方块（不是一次性全给N个），有且仅有一个位置能摆放这个方块
: ，方块可以旋转（90，180，270度）。要求打印出拼好的图案（即所有方块的摆放位置
: 和旋转角度）。
: 我当时的想法是，用一个矩阵储存方块在图案中的位置和角度，一个链表储存图案的边
: 缘（逆时针地）。每输入一个方块，就拿它的4条边跟链表中的边逐个比较，找到了就
: 记下它的位置和角度，还要注意如果方块的边跟图案中超过1条的边相邻的话（直角的
: 位置），所有邻边必须相同。找到摆放位置后需要从链表中删除一些边和插入一些边。
: 即使是像我这个简单的思路，写出bug free的code来还是很费劲啊。哎。。
|
C*Y
发帖数: 736 | 4 对，例子用的PHP，不过题目说可以用任何语言写。当时我也是用C++
不过题目没说数据规模有多大，那个只是例子，可能是我想复杂了
刚开始的时候我想边界只有55种，所以可以把图案的边界放在hash里，每次搜索只要O(
1)的时间，一共只要O(N)的时间。到真正写code的时候还是不熟啊，后来觉得可能不够
时间了改成链表好像比较省code，就这么过了3小时。。。刚看到题目的时候还想这东
西居然要2小时啊，结果做起来成这样子。。哎。。
【在 s*********t 的大作中提到】
: 这个公司我前一阵申请了，题目也做出来了，可惜人家只招local，唉。。
: 这个题目就是考察基本的编程逻辑，从题目给的数据规模限制来看，就是要暴力解法。
: 我记得要求是用PHP写，是不
|
