ZOJ Problem Set – 1056 The Worm Turns

原题如下：

The Worm Turns

Time Limit: 1 Second Memory Limit: 32768 KB

Worm is an old computer game. There are many versions, but all involve maneuvering a "worm" around the screen, trying to avoid running the worm into itself or an obstacle.

We'll simulate a very simplified version here. The game will be played on a 50 x 50 board, numbered so that the square at the upper left is numbered (1, 1). The worm is initially a string of 20 connected squares. Connected squares are adjacent horizontally or vertically. The worm starts stretched out horizontally in positions (25, 11) through (25, 30), with the head of the worm at (25, 30). The worm can move either East (E), West (W), North (N) or South (S), but will never move back on itself. So, in the initial position, a W move is not possible. Thus the only two squares occupied by the worm that change in any move are its head and tail. Note that the head of the worm can move to the square just vacated by the worm's tail.

You will be given a series of moves and will simulate the moves until either the worm runs into itself, the worm runs off the board, or the worm successfully negotiates its list of moves. In the first two cases you should ignore the remaining moves in the list.

Input

There will be multiple problems instances. The input for each problem instance will be on two lines. The first line is an integer n (<100) indicating the number of moves to follow. (A value of n = 0 indicates end of input.) The next line contains n characters (either E, W, N or S), with no spaces separating the letters, indicating the sequence of moves.

Output

Generate one line of output for each problem instance. The output line should be one of the follow three:

The worm ran into itself on move m.
The worm ran off the board on move m.
The worm successfully made all m moves.

Where m is for you to determine and the first move is move 1.

Sample Input

18
NWWWWWWWWWWSESSSWS
20
SSSWWNENNNNNWWWWSSSS
30
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
13
SWWWWWWWWWNEE
0

Sample Output

The worm successfully made all 18 moves.
The worm ran into itself on move 9.
The worm ran off the board on move 21.
The worm successfully made all 13 moves.

Source: East Central North America 2001, Practice

这个题目分析一下其实不是很难，应该算是简单题吧，实现的是贪吃蛇的基本算法，写完这个，再加上一些界面的东西的话，贪吃蛇也就出来了（不要告诉我你不知道贪吃蛇，这可是诺基亚手机的经典游戏啊）。我的解法如下：

  1: #include<iostream>
  2: #include<vector>
  3: #include<string>
  4: #include<sstream>
  5: 
  6: using namespace std;
  7: 
  8: /*
  9: worm information
 10: */
 11: const int HEAD = 1;          //indicate the head of the worm
 12: const int TAIL = -1;         //indicate the tail of the worm
 13: const int BODY = 0;          //indicate the body of the worm
 14: const int BEGIN_Y = 25;       //intial value of x
 15: const int BEGIN_X = 11;       //intial value of y
 16: const int WORM_SIZE = 20;    //indicate the length of the worm
 17: /*
 18: Board information
 19: */
 20: const int BOARD_WIDTH = 50;        //indicate the width of the board
 21: const int BOARD_HEIGHT = 50;       //indicate the height of the board
 22: 
 23: /*
 24: ERROR information
 25: */
 26: const int RUN_INTO_ITSELF = 1;     //indicate the worm run into itself
 27: const int RUN_OFF_BOARD = 2;       //indicate the worm run off the board
 28: const int SUCCEED = 0;               //indicate the worm moves successful
 29: 
 30: /*
 31: contain a worm square information ,include the postion(x,y),
 32: and which part of this square in the worm(positon,head,body,tail)
 33: */
 34: struct WORM 
 35: {
 36:     int x;
 37:     int y;
 38:     int position;
 39:     WORM(int xx = 0,int yy = 0,int Position = BODY):x(xx),y(yy),position(Position){}
 40:     WORM(const WORM& oldWorm):x(oldWorm.x),y(oldWorm.y),position(oldWorm.position){}
 41: };
 42: bool operator==(WORM a,WORM b)
 43: {
 44:     if(a.x == b.x && a.y == b.y)
 45:     {
 46:         return true;
 47:     }
 48:     return false;
 49: }
 50: 
 51: /*
 52: update the information of the tail and head
 53: */
 54: int UpdateTail(vector<WORM>& worm, WORM& oldTail)//update tail 
 55: {
 56:     size_t oldTailIndex = 0;
 57:     for(;oldTailIndex < worm.size(); oldTailIndex++)
 58:     {
 59:         if(worm[oldTailIndex] == oldTail)
 60:         {
 61:             worm[(oldTailIndex + 1)%worm.size()].position = TAIL;
 62:             oldTail = worm[(oldTailIndex + 1)%worm.size()];
 63:             break;
 64:         }
 65:     }
 66:     return oldTailIndex;
 67: }
 68: 
 69: int UpdateHead(vector<WORM>& worm, WORM& oldHead,char direction,int position)//update head
 70: {
 71:     switch(direction)
 72:     {
 73:     case 'N': 
 74:         oldHead.y--;
 75:         break;
 76:     case 'S':
 77:         oldHead.y++;
 78:         break;
 79:     case 'W':
 80:         oldHead.x--;
 81:         break;
 82:     case 'E':
 83:         oldHead.x++;
 84:         break;
 85:     default:
 86:         break;
 87:     }
 88: 
 89:     if(oldHead.y < 1 || oldHead.y > BOARD_HEIGHT || oldHead.x < 1 || oldHead.x > BOARD_WIDTH)
 90:     {
 91:         return RUN_OFF_BOARD;
 92:     }
 93: 
 94:     for(size_t i = 0; i < worm.size(); i++)
 95:     {
 96:         if(i == position)
 97:         {
 98:             continue;
 99:         }
100:         if(worm[i] == oldHead)
101:         {
102:             return RUN_INTO_ITSELF;
103:         }
104:     }
105: 
106:     worm[position] = oldHead;
107:     return SUCCEED;
108: }
109: 
110: int main(void)
111: {
112:     for(int steps;cin>>steps && steps;)
113:     {
114:         vector<WORM> worm;//store the information of a worm
115:         /*intial worm information*/
116:         WORM wormTail( WORM( BEGIN_X, BEGIN_Y, TAIL ) );//worm's tail position
117:         worm.push_back(wormTail);
118:         int x = 1;
119:         for(; x <= WORM_SIZE - 2; x++) //worm's body information
120:         {
121:             worm.push_back(WORM(BEGIN_X + x,BEGIN_Y));
122:         }
123:         WORM wormHead( WORM( BEGIN_X + x,BEGIN_Y,HEAD ) );
124:         worm.push_back(wormHead);//worm's head position
125: 
126:         int currentStep = 0;                //indicate step the worm goes
127:         int oldTailIndex = 0;                //indicate the position of the old tail
128:         int ErrorInfo = 0;                    //the information after the worm goes
129: 
130:         string directions;
131:         cin>>directions;
132:         istringstream is(directions);
133:         for(char direction;currentStep < steps && is>>direction;currentStep ++)
134:         {
135:             oldTailIndex = UpdateTail(worm,wormTail);
136:             ErrorInfo = UpdateHead(worm,wormHead,direction,oldTailIndex);
137:             if(ErrorInfo > 0)
138:             {
139:                 break;
140:             }
141:         }
142: 
143:         switch(ErrorInfo)
144:         {
145:         case RUN_INTO_ITSELF:
146:             cout<<"The worm ran into itself on move "<<currentStep + 1<<"."<<endl;
147:             break;
148:         case RUN_OFF_BOARD:
149:             cout<<"The worm ran off the board on move "<<currentStep + 1<<"."<<endl;
150:             break;
151:         case SUCCEED:
152:             cout<<"The worm successfully made all "<<currentStep<<" moves."<<endl;
153:             break;
154:         default:
155:             break;
156:         }
157:     }
158:     return 0;
159: }

其实想想简单啦，最主要的就是头和尾的更新问题，如上述黄色部分。在这里，我选择了自定义的一个结构来存储一条虫的每一个节点的信息，当然包括该节点的坐标，还有位置（头，身体，尾）。具体的，请见代码，没什么难度，就不分析了。