题目描述
小喻最喜欢玩的游戏就是消消乐，这款游戏的规则如下：
在一个由 N×N 个方格组成的棋盘中，每个方格都是红、黄、蓝、绿这 4 种颜色中的一种，玩家可以点击最底的一行中任意一个方格，点击后与这个方格相邻所有的同色的方块都会被消除，消除的方格上方的方格会因为重力作用垂直落下填补出现的空位。
请你设计一个程序，如果小喻点击最底这行左起第 M 个格子，输出棋盘的情况。
输入格式
第一行两个整数 N,M, N表示棋盘的规模，妈妈点击最底行从左数起的第 M 个方块。
接下来的 N行，每行 N 个由1,2,3,4 组成的数字，表示点击前的棋盘，每个数字间用一个空格隔开。
输出格式
输出 N 行，每行 N个数表示妈妈点击后的棋盘情况，没有方格的位置输出 0 ，每个数字间用一个空格隔开。
样例输入
4 2
1 2 3 4
4 2 4 4
3 4 4 3
1 4 4 3
样例输出
1 0 0 0
4 0 0 0
3 2 0 3
1 2 3 3
数据范围
对于%100%的数据：1≤M≤N≤100。
#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int h=1,r=1;
struct st
{
int x,y;
}q[10010];
int a[110][110];
int n,m,s=1;
int colornum;
void bfs()
{
int xx,yy;
s=r;
while(r>=h)
{
a[q[r].x][q[r].y]=0;
for(int i=0;i<4;i++)
{
xx=q[r].x+dx[i];
yy=q[r].y+dy[i];
if(xx>0&&yy>0&&xx<=n&&yy<=n&&a[xx][yy]==colornum)
{
s++;
q[s].x=xx;
q[s].y=yy;
a[xx][yy]=0;
}
}
r=s;
h++;
}
}
int main()
{
cin>>n>>m;
q[1].x=m;
q[1].y=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(i==n&&j==m)
{
colornum=a[i][j];
}
}
bfs();
int l;
for(int i=1;i<=n;i++)
{
for(int j=n-1;j>=1;j--)
{
l=j;
while(a[l+1][i]==0&&l!=n)
{
a[l+1][i]=a[l][i];
a[l][i]=0;
l++;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
/*
4 2
1 2 3 4
4 2 4 4
3 4 4 3
1 4 4 3
*/
又是BFS
暂时做好了消除，下落还没做
#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int h=1,r=1;
struct st
{
int x,y;
}q[10010];
int a[110][110];
int n,m,s=1;
int colornum;
void bfs()
{
int xx,yy;
s=r;
while(r>=h)
{
a[q[r].x][q[r].y]=0;
cout<<q[r].x<<" "<<q[r].y<<" "<<"Right"<<endl;
for(int i=0;i<4;i++)
{
xx=q[r].x+dx[i];
yy=q[r].y+dy[i];
if(xx>0&&yy>0&&xx<=n&&yy<=n&&a[xx][yy]==colornum)
{
s++;
q[s].x=xx;
q[s].y=yy;
a[xx][yy]=0;
}
}
r=s;
h++;
}
}
int main()
{
cin>>n>>m;
q[1].x=m;
q[1].y=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(i==n&&j==m)
{
colornum=a[i][j];
}
}
bfs();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
#define maxn 100001
int vis[maxn],step[maxn];
queue<int >q; //定义全局队列
int bfs(int n,int m)
{
int head,next;
q.push(n);
step[n]=0;
vis[n]=1;
while(!q.empty()) //队列不为空则一直循环
{
head=q.front(); //获取队首元素，然后弹出
q.pop();
for(int i=1;i<=3;i++) //3种前进方式
{
if(i==1)
next=head-1;
else if(i==2)
next=head+1;
else
next=head*2;
if(next<0||next>=maxn) //判断是否越界
continue;
if(!vis[next]) //判断是否已经来过该点
{
q.push(next); //将子节点插入队尾
step[next]=step[head]+1; //步数加 1
vis[next]=1; //标记已经来过的点
}
if(next==m) //找到目标点
return step[next];
}
}
}
int main()
{
int n,m;
mem(vis,0);
while(!q.empty())
q.pop();
cin>>n>>m;
if(n>=m)
cout<<n-m;
else
cout<<bfs(n,m);
return 0;
}
BFS BFS简单的BFS...