7-3 贪吃蛇
题目:
这是一个类似于贪吃蛇的程序,一条蛇,在一个矩阵(方阵)中前进,从左上角(0,0)开始,依次吃掉矩阵中的数据,当它碰壁或者发现前进方向上的元素已经被吃过,就转向下一个方向并继续前进,转向的规则依次是:左,上,右,下。n阶方阵的元素顺序按行存储的,例如,n=2,则方阵的元素如下:
0 1
2 3
如n=4,则方阵是:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入格式:
输入方阵的阶数n
输出格式:
在一行上按蛇吃过的元素的顺序输出,其中用空格分隔,行尾有一个空格
输入样例:
在这里给出一组输入。例如:
4
输出样例:
在这里给出相应的输出。例如:
0 1 2 3 7 11 15 14 13 12 8 4 5 6 10 9
代码实现:
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
const int N = 1010;
int g[N][N];
int n;
int d[N][N];
bool st[N][N];
typedef pair<int, int>PII;
stack<PII>q;
void bfs(int n)
{
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };//这里分别对应,左,上,右,下四个操作。
q.push({ 0,0}); d[0][0] = 0; st[0][0] = 1;//把起点压进去
while (q.size()!=n*n)//当栈里面吃满所有的数时,结束
{
for (int i = 0; i < 4; i++)
{
auto t = q.top();
int X = t.first + dx[i], Y = t.second + dy[i];
while (X >= 0 && X < n && Y >= 0 && Y < n &&st[X][Y] == 0)
{
q.push({ X,Y });
d[X][Y] = g[X][Y];
cout << d[X][Y] << ' ';//遍历到一次,输出一次
st[X][Y] = 1;
X += dx[i]; Y += dy[i];
}
}
}
}
int main()
{
int l = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
g[i][j] = l++;
//printf("%d \t", g[i][j]);
}//cout << endl;
}
//cout << endl;
cout << 0 <<' ';
bfs(n);
}