贪吃蛇
题目描述
【贪吃蛇】贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。
下面让我们来完成贪吃蛇游戏的模拟：
给定一个NM的数组ar，代表NM个方格组成的版图，贪吃蛇每次移动一个方格。若ar[i][j]=='H'，表示该方可为贪吃蛇的起始位置;若ar[i][j]=='F'，表示该方格为食物，若ar[i][j]=='E'，表示该方格为空格。
贪吃蛇初始长度为1，初始移动方向为向左。输入为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时贪吃蛇的长度。
贪吃蛇移动、吃食物和碰撞处理的细节见下面图示:
图一
图二
图三
图四
图五
图六
图 1:截取了贪吃蛇移动的一个中间状态，H表示蛇头，F表示食物，数字为蛇身体各节的 编号，蛇为向左移动，此时蛇头和食物已经相邻。
图 2:蛇头向左移动一格，蛇头和食物重叠，注意此时食物的格子成为了新的蛇头，第 1节 身体移动到蛇头位置，第 2节身体移动到第 1节身***置，以此类推，最后添加第 4节升 起到原来第 3节身体的位置。
图 3:蛇头继续向左移动一格，身体的各节按上述规则移动，此时蛇头已经和边界相邻，但 还未碰撞。
图 4:蛇头继续向左移动一格，此时蛇头已经超过边界，发生碰撞，游戏结束。
图 5和图 6给出一个蛇头和身体碰撞的例子，蛇为向上移动。图 5时蛇头和第 7节身体相 邻，但还未碰撞;图 6蛇头向上移动一格，此时蛇头和第 8节身体都移动到了原来第 7节 身体的位置，发生碰撞，游戏结束。
注意：
输入描述:
输入第 1行为空格分隔的字母，代表贪吃蛇的移动操作。字母取值为 U、D、L、R、G，其中U、D、L、R分别表示贪吃蛇往上、下、左、右转向，转向时贪吃蛇不移动，G表示贪吃蛇按 当前的方向移动一格。用例保证输入的操作正确。
第 2行为空格分隔的两个数，指定为 N和 M，为数组的行和列数。余下 N行每行是空格分 隔的 M个字母。字母取值为 H、F和 E，H表示贪吃蛇的起始位置，F表示食物，E表示该 方格为空。用例保证有且只有一个 H，而 F和 E会有多个。
输出描述:
输出一个数字为蛇的长度。
示 例:
输入:
D G G
3 3
F F F
F F H
E F E
输出:
1
输入第 1行为空格分隔的字母，代表贪吃蛇的移动操作。字母取值为 U、D、L、R、G，其中U、D、L、R分别表示贪吃蛇往上、下、左、右转向，转向时贪吃蛇不移动，G表示贪吃蛇按 当前的方向移动一格。用例保证输入的操作正确。
第 2行为空格分隔的两个数，指定为 N和 M，为数组的行和列数。余下 N行每行是空格分 隔的 M个字母。字母取值为 H、F和 E，H表示贪吃蛇的起始位置，F表示食物，E表示该 方格为空。用例保证有且只有一个 H，而 F和 E会有多个。
输出描述:
输出一个数字为蛇的长度。
示 例:
输入:
D G G
3 3
F F F
F F H
E F E
输出:
1
C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
string command;
getline(cin, command);
vector<char> operateStr;
pair<int, int>;
queue<pair<int, int>> Q;
for (int i = 0; i < command.length(); i++)
{
if (command[i] != ' ')
{
operateStr.push_back(command[i]);
}
}
//string num;
//getline(cin,num);
int m, n;
cin >> m >> n;
while (getchar() != '\n')
{
continue;
};
vector<string> inputs;
string str;
while (getline(cin, str))
{
if (!str.empty())
{
inputs.push_back(str);
}
else
{
break;
}
}
vector<vector<char>> map(m);
//vector<pair<int,int>,int> hashMap(m);
for (int i = 0; i < inputs.size(); i++)
{
for (int j = 0; j < inputs[i].size(); j++)
{
if (inputs[i][j] != ' ')
{
map[i].push_back(inputs[i][j]);
}
}
}
list<pair<int, int>> lists;
char opera = ' ';
//遍历map,找出头结点。
for (int i = 0; i < map.size();i++)
{
for (int j = 0; j < map[i].size(); j++)
{
if(map[i][j] == 'H')
{
lists.push_front(make_pair(i, j));
map[i][j] = 'E';
}
}
}
for (int i = 0; i < operateStr.size(); i++)
{
if(operateStr[i] == 'G')
{
pair<int, int> f = lists.front();
int ha = f.first;
int le = f.second;
//U、D、L、R
if(opera == 'U')
{
if(ha - 1 < 0)
{
break;
}else
{
list<pair<int, int>>::iterator it;
it = find(lists.begin(), lists.end(), make_pair(ha - 1, le));
if (it != lists.end())
{
break;
}
if(map[ha - 1][le] == 'F')
{
//如果向上走是食物，
//如果当前链表中没有此节点,则将当前节点加入链表中
//同时清空链表的食物
lists.push_front(make_pair(ha - 1, le));
map[ha - 1][le] == 'E';
}
//如果当前节点是空节点，则向前一步，加入当前节点，且清空链表尾部节点
else if(map[ha - 1][le] == 'E')
{
lists.push_front(make_pair(ha - 1, le));
lists.pop_back();
}
}
}
else if (opera == 'D')
{
if (ha + 1 >= m)
{
break;
}
else
{
list<pair<int, int>>::iterator it;
it = find(lists.begin(), lists.end(), make_pair(ha + 1, le));
if (it != lists.end())
{
break;
}
if (map[ha + 1][le] == 'F')
{
//如果向上走是食物，
//如果当前链表中没有此节点,则将当前节点加入链表中
//同时清空链表的食物
lists.push_front(make_pair(ha + 1, le));
map[ha + 1][le] == 'E';
}
//如果当前节点是空节点，则向前一步，加入当前节点，且清空链表尾部节点
else if (map[ha + 1][le] == 'E')
{
lists.push_front(make_pair(ha + 1, le));
lists.pop_back();
}
}
}
else if (opera == 'L')
{
if (le - 1 < 0)
{
break;
}
else
{
list<pair<int, int>>::iterator it;
it = find(lists.begin(), lists.end(), make_pair(ha, le - 1));
if (it != lists.end())
{
break;
}
if (map[ha][le - 1] == 'F')
{
//如果向上走是食物，
//如果当前链表中没有此节点,则将当前节点加入链表中
//同时清空链表的食物
lists.push_front(make_pair(ha, le - 1));
map[ha][le - 1] == 'E';
}
//如果当前节点是空节点，则向前一步，加入当前节点，且清空链表尾部节点
else if (map[ha][le - 1] == 'E')
{
lists.push_front(make_pair(ha, le - 1));
lists.pop_back();
}
}
}
else if (opera == 'R')
{
if (le + 1 >= n)
{
break;
}
else
{
list<pair<int, int>>::iterator it;
it = find(lists.begin(), lists.end(), make_pair(ha, le + 1));
if (it != lists.end())
{
break;
}
if (map[ha][le + 1] == 'F')
{
//如果向上走是食物，
//如果当前链表中没有此节点,则将当前节点加入链表中
//同时清空链表的食物
lists.push_front(make_pair(ha, le + 1));
map[ha][le + 1] == 'E';
}
//如果当前节点是空节点，则向前一步，加入当前节点，且清空链表尾部节点
else if (map[ha][le + 1] == 'E')
{
lists.push_front(make_pair(ha, le + 1));
lists.pop_back();
}
}
}
}else
{
opera = operateStr[i];
}
}
int len = lists.size();
cout << "最终结果为：" << len;
system("pause");
return 0;
}
