- 浏览: 150603 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
听说名字可以很长:
...
[翻译]Boost Graph库简介 -
utensil:
很多人来到我的博客,都是为了搜索Eclipse的黑底配色方案。 ...
Eclipse之舒适化打造(黑底TextMate配色方案、Jodeclipse等) -
王牌海盗:
感谢博主,正好在寻找黑底的eclipse配色方案,刚刚下载用了 ...
Eclipse之舒适化打造(黑底TextMate配色方案、Jodeclipse等) -
utensil:
dashandian 写道这两个网站现在都打不开了啊现在搬迁到 ...
wxWidgets官方论坛中文版块开张!欢迎光临! -
dashandian:
这两个网站现在都打不开了啊
wxWidgets官方论坛中文版块开张!欢迎光临!
Problem
You find yourself standing outside of a perfect maze. A maze is defined as "perfect" if it meets the following conditions:
- It is a rectangular grid of rooms, R rows by C columns.
- There are exactly two openings on the outside of the maze: the entrance and the exit. The entrance is always on the north wall, while the exit could be on any wall.
- There is exactly one path between any two rooms in the maze (that is, exactly one path that does not involve backtracking).
You decide to solve the perfect maze using the "always turn left" algorithm, which states that you take the leftmost fork at every opportunity. If you hit a dead end, you turn right twice (180 degrees clockwise) and continue. (If you were to stick out your left arm and touch the wall while following this algorithm, you'd solve the maze without ever breaking contact with the wall.) Once you finish the maze, you decide to go the extra step and solve it again (still always turning left), but starting at the exit and finishing at the entrance.
The path you take through the maze can be described with three
characters: 'W' means to walk forward into the next room, 'L' means to
turn left (or counterclockwise) 90 degrees, and 'R' means to turn right
(or clockwise) 90 degrees. You begin outside the maze, immediately
adjacent to the entrance, facing the maze. You finish when you have
stepped outside the maze through the exit. For example, if the entrance
is on the north and the exit is on the west, your path through the
following maze would be WRWWLWWLWWLWLWRRWRWWWRWWRWLW
:
If the entrance and exit were reversed such that you began outside
the west wall and finished out the north wall, your path would be WWRRWLWLWWLWWLWWRWWRWWLW
.
Given your two paths through the maze (entrance to exit and exit to
entrance), your code should return a description of the maze.
Input
The first line of input gives the number of cases, N . N test cases follow. Each case is a line formatted as
entrance_to_exit exit_to_entrance
All paths will be at least two characters long, consist only of the characters 'W', 'L', and 'R', and begin and end with 'W'.
Output
For each test case, output one line containing "Case #x :" by itself. The next R lines give a description of the R by C maze. There should be C characters in each line, representing which directions it is possible to walk from that room. Refer to the following legend:
1 | Yes | No | No | No |
2 | No | Yes | No | No |
3 | Yes | Yes | No | No |
4 | No | No | Yes | No |
5 | Yes | No | Yes | No |
6 | No | Yes | Yes | No |
7 | Yes | Yes | Yes | No |
8 | No | No | No | Yes |
9 | Yes | No | No | Yes |
a | No | Yes | No | Yes |
b | Yes | Yes | No | Yes |
c | No | No | Yes | Yes |
d | Yes | No | Yes | Yes |
e | No | Yes | Yes | Yes |
f | Yes | Yes | Yes | Yes |
Limits
1 ≤ N ≤ 100.
Small dataset
2 ≤ len(entrance_to_exit) ≤ 100, 2 ≤ len(exit_to_entrance) ≤ 100.
Large dataset
2 ≤ len(entrance_to_exit) ≤ 10000, 2 ≤ len(exit_to_entrance) ≤ 10000.
Sample
Input |
2
WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW
|
Output |
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3
|
#include <iostream> #include <fstream> #include <map> #include <iomanip> //#define MY_DEBUG using namespace std; /* +----------->i | | | V j */ struct maze_coord { maze_coord() { i = j = 0; } maze_coord(int i_, int j_) { i = i_; j = j_; } int i; int j; //for being put into map bool operator < (const maze_coord& other) const { return (j < other.j) || (j == other.j && i < other.i); } //for calculating the size of the maze maze_coord operator - (const maze_coord& other) const { return maze_coord(i - other.i, j - other.j); } }; enum direction { north = 1, south = 1<<1, west = 1<<2, east = 1<<3 }; #ifdef MY_DEBUG //direction symbol const char* symbol = " ^V < >"; #endif //clockwise cycle const direction cycle[4] = {north, east, south, west}; //helper function to turn the direction //turn for |n|*90 degrees //n<0 to turn left //n>0 to turn right direction turn(direction d, int n = 1) { for(int i = 0; i < 4; i++) { if(cycle[i] == d) { i = (i+n)%4; return cycle[(i>=0)?i:(4+i)]; } } } // high 4 bits are used to mark known/unknown status // low 4 bits are used to mark can/cant walk status // order: // east west south north typedef unsigned char room_state; typedef map<maze_coord, room_state> Maze; //Rat will walk in the maze, and mark the state of every room class Rat { public: Rat(Maze& maze) :m_maze(maze) { m_heading = south; m_coord.i = 0; m_coord.j = -1; } //W void Walk(bool is_next_step_walk) { //If there is record for the last room //Mark it as walkable if(m_maze.count(m_coord)) { m_maze[m_coord] |= m_heading; m_maze[m_coord] |= m_heading<<4; } //Walk switch(m_heading) { case north : --m_coord.j;break; case south : ++m_coord.j;break; case west : --m_coord.i;break; case east : ++m_coord.i;break; } //If there is no record for the current room //Clear its state if(!m_maze.count(m_coord)) m_maze[m_coord] = 0x00; direction walkable_wall = turn(m_heading, 2); m_maze[m_coord] |= walkable_wall; //it's walkable m_maze[m_coord] |= walkable_wall<<4; //it's known //WW if(is_next_step_walk) { //left direction unwalkable_wall = turn(m_heading, -1); m_maze[m_coord] |= unwalkable_wall<<4; //it's known to be unwalkable } #ifdef MY_DEBUG cout << "Walk to "; cout << dec << '(' << m_coord.i << ',' << m_coord.j << ')' << ''; cout << "Heading "<< symbol[m_heading] << ":"; cout << hex << (unsigned int)m_maze[m_coord] << endl; #endif } //L void TurnLeft() { //turn left m_heading = turn(m_heading, -1); //left m_maze[m_coord] |= m_heading; //it's walkable m_maze[m_coord] |= m_heading<<4; //it's known #ifdef MY_DEBUG cout << "Turn left " << ''; cout << "Heading "<< symbol[m_heading] << ":"; cout << hex << (unsigned int)m_maze[m_coord] << endl; #endif } //R void TurnRight() { //left direction unwalkable_wall = turn(m_heading, -1); m_maze[m_coord] |= unwalkable_wall<<4; //it's known to be unwalkable //forward unwalkable_wall = m_heading; m_maze[m_coord] |= unwalkable_wall<<4; //it's known to be unwalkable //right m_heading = turn(m_heading, 1); //turn right m_maze[m_coord] |= m_heading; //it's walkable m_maze[m_coord] |= m_heading<<4; //it's known #ifdef MY_DEBUG cout << "Turn right " << ''; cout << "Heading "<< symbol[m_heading] << ":"; cout << hex << (unsigned int)m_maze[m_coord] << endl; #endif } //RR void TurnBack() { //left direction unwalkable_wall = turn(m_heading, -1); m_maze[m_coord] |= unwalkable_wall<<4; //it's known to be unwalkable //forward unwalkable_wall = m_heading; m_maze[m_coord] |= unwalkable_wall<<4; //it's known to be unwalkable //right unwalkable_wall = turn(m_heading, 1); m_maze[m_coord] |= unwalkable_wall<<4; //it's known to be unwalkable //turn back m_heading = turn(m_heading, 2); #ifdef MY_DEBUG cout << "Turn back " << ''; cout << "Heading "<< symbol[m_heading] << ":"; cout << hex << (unsigned int)m_maze[m_coord] << endl; #endif } //Clear the record for current room //call it after gets out of the exit and TurnBack void ClearCurrentRoom() { m_maze.erase(m_coord); #ifdef MY_DEBUG cout << "+++++++++++++" << endl; #endif } //for speeding up the programming, break the encapsulation a little direction m_heading; maze_coord m_coord; Maze& m_maze; }; int main(int argc, char* argv[]) { #ifndef MY_DEBUG //Only for memerizing usage for myself if(argc != 3) { cout << "Usage: atl INPUT_FILE OUTPUT_FILE" << endl; return 0; } ifstream fin(argv[1]); //!! ofstream fout(argv[2]); //!! #else ifstream fin("B-large.in"); //!! ofstream fout("test.out"); //!! #endif //How many cases in total? int case_max; fin >> case_max; fin.ignore(); // '' char tmp; for(int cur_case = 1; cur_case <= case_max; cur_case++) { Maze maze; Rat rat(maze); while((tmp = fin.get()) != '')//!! { switch(tmp) { case 'W' : rat.Walk(fin.peek() == 'W'); break; case 'L' : rat.TurnLeft(); break; case 'R' : if(fin.get() == 'R') rat.TurnBack(); else { fin.unget(); rat.TurnRight(); } break; case ' ' ://!! rat.TurnBack(); rat.ClearCurrentRoom(); break; } } rat.ClearCurrentRoom(); maze_coord top_left = maze.begin()->first; maze_coord bottom_right = (--maze.end())->first; //This style works, but I guess it's slower #if 0 fout << "Case #" << dec << cur_case << ':' << endl; for(int row = top_left.j; row <= bottom_right.j; row++) { for(int col = top_left.i; col <= bottom_right.i; col++) { fout << hex << (unsigned int)(0x0f&maze[maze_coord(col, row)]); } fout << endl; } #endif //Start writing the file fout << "Case #" << dec << cur_case << ':' << endl; //in non-debug mode, show the progress #ifndef MY_DEBUG cout << "Case #" << dec << cur_case << endl; #endif int max_col = (bottom_right - top_left).i; int cur_col = 0; for(Maze::iterator it = maze.begin(); it != maze.end(); ++it) { #ifdef MY_DEBUG cout << hex << (unsigned int)(*it).second << ' '; #endif fout << hex << (unsigned int)(0x0f&(*it).second); if(cur_col == max_col) { fout << endl; #ifdef MY_DEBUG cout << endl; #endif cur_col = 0; continue; } ++cur_col; } } return 0; }
发表评论
-
RAII和垃圾收集
2009-05-14 20:36 1891Utensil按: 此文转自CSD ... -
ofstream与ate的故事
2009-04-21 21:26 4792很久之前,我和Swalky在写Huffman Tree压缩的 ... -
《代码之美》简单笔记
2009-04-21 10:53 2111《代码之美》一书的简单笔记。附件是网上搜索来的《代码之美》英文 ... -
我写的第一个类:BasedNum
2007-08-29 19:42 975//BasedNum.h #include <io ... -
c++资源之不完全导引
2007-12-26 20:05 1103撰文/曾毅陶文 转自:ht ... -
Google Code Jam之Alien Numbers之我的解答
2008-06-24 23:35 1831由于时间的限制,程序有些地方的容错性不够,以//!! ... -
[翻译]Boost Graph库简介
2008-08-18 17:48 3100转载请注明: 作者:Utensil 博客:http://u ... -
编程的未来
2008-10-01 08:57 2631有一句话,我觉得对程序员是至理名言:编程未来的趋势是库,动态的 ... -
隐性类型转换的突发奇想与失望
2008-12-22 21:46 1234在C++中,如果为自定义类型(class)定义了类型转换操作符 ... -
Objective-C语法快速参考
2008-12-23 22:20 2468Utensil按:对wxWidgets的Mac Port一直相 ... -
享受Code::Blocks编辑快感的几个关键
2008-12-24 09:05 2382感谢Loaden的补充。此文是对帖子http://wxforu ...
相关推荐
google code jam
A solution of contest problem in Google Code Jam
google codejam2014源代码
抱歉,CSDN目前无法设置免费资源,感兴趣的话在我博客下留言,我可以用邮件发给你。 Small input of Google code jam - World Finals 2017-Problem A. Dice Straight
2008 Google Code Jam 第三轮网赛,lym和windy两位大牛的代码,很值得学习!
自己写的源码,希望各位看官指出不足之处,好交流进步
Google Codejam
Google Code Jam 练习题的解决方案 在与给定问题具有相同标题的 java 类中找到解决方案。 在这一点上,所有解决方案都针对在明确提到的作为良好起点的问题 每个解决方案都需要从命令行运行一个参数,一个包含问题...
Google Code Jam统计用于检查Google Code Jam轮次统计信息的网站为什么? 已经有一些很棒的网站(例如和 ),但它们仅提供截至2017年的数据。该网站使用于2018年推出的新Google Competitions API来收集并显示有关...
我的Google Code Jam旅程记录我的GCJ旅程的回购。 每年更新。 年日期圆形的结果评论2020年5月2日1C2020年4月20日1B数学太多2020年4月11日1A2020年4月4日资质做得好2019年5月4日1C搞砸了2019年4月28日1B需要更多练习...
代码堵塞 Google Code Jam 解决方案
谷歌codejam 我对Google Codejam的解决方案
这个资料库包含我在2021年之前解决Google Code Jam竞赛问题的解决方案,无论是在竞赛期间提交还是经过深思熟虑。 源代码使用Java,每个源文件都包含对所用算法的描述。 src目录中的Java软件包包含按Code Jam版本和...
README File for 8051 Jam Byte-Code Player v1.0 What Does v1.0 Support? The source code supports programming devices from the 8051 family of microprocessors. Jam Byte-Code (.jbc) files from the ...
googlecodejam 我的Google Code Jam解决方案内容(比赛中的结果)-当前20 质量: Reversort(正确)-已解决月亮和雨伞(正确,正确,吗?)-已解决| 不是测试用例3 Reversort Engineering(正确,错误的答案)-特定...
Codejam 我的Google Code Jam解决方案
该存储库包含我针对和Distributed Google Code Jam 2018中的问题的解决方案。这些解决方案“按原样”提供-我不保证它们将按预期运行。 指示 您可以通过发出以下命令来编译所有Google Code Jam问题: $ make 如果...
Google Code Jam for I / O for Women 2021年4月17日我的解决方案(在Java SDK 11中)针对Google Code Jam for Women 2021的解决方案。您可以在此处查看比赛: : 请客气; 这是一个正在进行的工作! 问题摘要如下。 ...
Google-Codejam Google举办时间最长的全球编码竞赛Code Jam呼吁世界各地的程序员日以继夜地解决具有挑战性的算法难题。 参赛者将进行四轮在线托管竞赛,以参加每年在不同的Google国际办公室举行的年度Code Jam世界总...
谷歌-codejam-2015 我为 Google Code Jam 2015 所做的一切