浏览 1422 次
锁定老帖子 主题:joj 1034: Worm Turns
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-04-06
http://acm.jlu.edu.cn/joj/showproblem.php?pid=1034
这道题类似于贪吃蛇游戏,让你模拟Worm移动,看第几步跑出board,第几步跑到自己身上,全部完成。所以算法就是模拟。 #include<iostream> #include<list> #include<string> using namespace std; struct Square{ int x; int y; }; const int ROWS = 51; const int COLS = 51; list<Square> worm; void init_worm(){ worm.clear(); int i = 25; int j = 11; for(; j <= 30; j++){ Square s; s.x = i; s.y = j; worm.push_front(s); } } bool in_bound(int i,int j){ return i >= 1 && i < ROWS-1 && j >= 1 && j <= COLS-1; } bool run_into_self(int x, int y){ list<Square>::iterator it = worm.begin(); list<Square>::reverse_iterator rit = worm.rbegin(); if(rit->x == x && rit->y == y)//deal with the tail specially return false; for(; it != worm.end(); it++){ if(it->x == x && it->y == y){ return true; } } return false; } bool move(int i,int j,int current_step){ Square head = worm.front(); int x = head.x + i; int y = head.y + j; if( !in_bound(x,y) ){ cout << "The worm ran off the board on move " << current_step << "." << endl; return false; }else if( run_into_self(x,y) ){ cout << "The worm ran into itself on move " << current_step << "." << endl; return false; }else{ head.x = x; head.y = y; worm.push_front(head); worm.pop_back(); return true; } } int main(){ int move_steps; while(cin >> move_steps,move_steps){ init_worm(); int i; bool flag; string moves; cin >> moves; for(i = 1; i <= move_steps; i++){ flag = true; char ch = moves[i-1]; switch(ch){ case 'E': if(!move(0,1,i)) flag = false; break; case 'W': if(!move(0,-1,i)) flag = false; break; case 'N': if(!move(-1,0,i)) flag = false; break; case 'S': if(!move(1,0,i)) flag = false; break; defalut: break; } if(!flag) break; } if(i == move_steps + 1) cout << "The worm successfully made all " << move_steps << " moves." << endl; } return 0; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |