题目大意:贪吃蛇的简化版,给出一串操作命令,求蛇的最终状态是死是活。
解法:这条蛇一共20格的长度,所以用一个20个元素的队列表示,队列的每个元素是平面的坐标。每读入一条指令,判断其是否越界,是否咬到了自己。若都没有,把改点压入队列,front元素弹出。
参考代码:
#include<iostream>
#include<queue>
#include<string>
using namespace std; struct Point{
int r;
int c;
}; queue<Point> worm; bool isItself(queue<Point>,Point); int main(){
int i,n;
char str[102];
Point temp;
char x;
while(cin>>n&&n!=0){
while(!worm.empty())
worm.pop();
for(i=11;i<=30;i++){
temp.c=i;
temp.r=25;
worm.push(temp);
}
cin>>str;
i=1;
while(i<=n){
x=str[i-1];
temp=worm.back();
if(x=='W'){
temp.c-=1;
if((temp.c)<1){
cout<<"The worm ran off the board on move "<<i<<'.'<<endl;
break;
}
if(isItself(worm,temp)){
cout<<"The worm ran into itself on move "<<i<<'.'<<endl;
break;
}
worm.push(temp);
worm.pop(); }else{
if(x=='E'){
temp.c+=1;
if((temp.c)>50){
cout<<"The worm ran off the board on move "<<i<<'.'<<endl;
break;
}
if(isItself(worm,temp)){
cout<<"The worm ran into itself on move "<<i<<'.'<<endl;
break;
}
worm.push(temp);
worm.pop();
}else{
if(x=='S'){
temp.r+=1;
if((temp.r)>50){
cout<<"The worm ran off the board on move "<<i<<'.'<<endl;
break;
}
if(isItself(worm,temp)){
cout<<"The worm ran into itself on move "<<i<<'.'<<endl;
break;
}
worm.push(temp);
worm.pop();
}else{
if(x=='N'){
temp.r-=1;
if((temp.r)<1){
cout<<"The worm ran off the board on move "<<i<<'.'<<endl;
break;
}
if(isItself(worm,temp)){
cout<<"The worm ran into itself on move "<<i<<'.'<<endl;
break;
}
worm.push(temp);
worm.pop();
}
}
}
} if(i==n)
cout<<"The worm successfully made all "<<n<<" moves."<<endl;
i++;
}
} return 0;
} bool isItself(queue<Point> worm,Point p){
int k;
queue<Point> w;
w=worm;
w.pop();
for(k=1;k<19;k++){
if(w.front().r==p.r&&w.front().c==p.c)
return true;
w.pop();
}
return false;
}