joj 1034: Worm Turns

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;
}