#include<iostream>
#include<cstdlib>
#include<bitset>
#include<conio.h>
#include<time.h>
#include <windows.h>
#include<queue>
#include<algorithm>
using namespace std;
 
struct node{
 int x, y;
};
 
const int size = 9;
//地圖大小
int Score;
//得分
 
 
int Map[size][size];
//主地圖
int Map_2[size][size];
//輔助地圖 用于顯示
int dropNumbe[size][size];
//下降距離統(tǒng)計
int bfsVis[size][size];
//bfs標(biāo)記數(shù)組
 
int xx[4] = { 0, 0, 1, -1 };
int yy[4] = { 1, -1, 0, 0 };
//方向調(diào)整數(shù)組
 
int random();
//隨機(jī)數(shù)產(chǎn)生
void initMap();
//地圖初始化
void updateMap(int flag);
//打印地圖
void printSqure(int i);
//形狀打印
void dropNumberCount();
//下落高度統(tǒng)計
void squreDrop();
//根據(jù)下落高度更新地圖
void reflashMap();
//下落后的地圖新元素添加
void mapCopy();
//數(shù)組復(fù)制
void displayUpdate();
//消失效果
bool updateCheck();
//檢測是否有符合消除條件，通過bfs消除
bool bfsCheck(int x, int y, int squre);
//bfs標(biāo)記及越界檢測
void Bfs(int x, int y);
 
 
 
int main()
{
 initMap();
 Score = 0;
 updateMap(1);
 while (true)
 {
 bool isUpdate = false;
 int x1, x2, y1, y2;
 cout << "please input x1,y1,x2,y2" << endl;
 cin >> x1 >> y1 >> x2 >> y2;
 mapCopy();
 swap(Map[x1][y1], Map[x2][y2]);
 
 updateMap(1);
 
 isUpdate = updateCheck();
 if (isUpdate){
 dropNumberCount();
 squreDrop();
 cout << endl;
 cout << "-------------------- drop" << endl;
 updateMap(1);
 
 cout << endl;
 cout << "-------------------- reflash" << endl;
 reflashMap();
 updateMap(1);
 
 
 while (isUpdate = updateCheck()){
 dropNumberCount();
 squreDrop();
 cout << endl;
 cout << "-------------------- drop" << endl;
 updateMap(1);
 
 cout << endl;
 cout << "-------------------- reflash" << endl;
 reflashMap();
 updateMap(1);
 system("pause");
 }
 }
 else{
 system("CLS");
 cout << "GAME OVER!" << endl;
 cout << "Total Score: ";
 cout << Score << endl;
 break;
 }
 
 }
}
 
int random(){
 //隨機(jī)數(shù)產(chǎn)生
 int temp;
 while (1){
 temp = rand() % 4;
 if (temp >= 0)return temp;
 }
}
void initMap(){
 //地圖初始化
 srand((int)time(0));
 for (int i = 1; i < size; i++){
 for (int j = 1; j < size; j++){
 Map[i][j] = (rand() % 4);
 }
 }
}
void printSqure(int i){
 //形狀打印
 switch (i){
 case -1:cout << "□"; break;
 case 0:cout << "■"; break;
 case 1:cout << "★"; break;
 case 2:cout << "▲"; break;
 case 3:cout << "●"; break;
 }
}
void updateMap(int flag){
 //打印地圖
 cout << "Current Score:";
 cout << Score << endl;
 for (int i = 0; i < size; i++){
 for (int j = 0; j < size; j++){
 if (i == 0){
 cout << j << " ";
 }
 else if (j == 0){
 cout << i;
 }
 else{
 int x;
 if (flag == 1)x = Map[i][j];
 else x = Map_2[i][j];
 printSqure(x);
 }
 }
 cout << endl;
 }
}
bool updateCheck(){
 //檢測是否有符合消除條件，通過bfs消除
 bool isUpdate = false;
 
 memset(bfsVis, 0, sizeof(bfsVis));
 
 for (int i = 1; i < size; i++){
 for (int j = 1; j < size; j++){
 if (bfsVis[i][j] == 0){
 bool mark = false;//存在三個一排
 if ((i - 1 >= 1) && (i + 1 < size)){
  int t1, t2, t3;
  t1 = Map[i][j];
  t2 = Map[i - 1][j];
  t3 = Map[i + 1][j];
  if ((t1 == t2) && (t1 == t3)){
  mark = true;
  isUpdate = true;
  }
 }
 if ((j - 1 >= 1) && (j + 1 < size)){
  int t1, t2, t3;
  t1 = Map[i][j];
  t2 = Map[i][j - 1];
  t3 = Map[i][j + 1];
  if ((t1 == t2) && (t1 == t3)){
  mark = true;
  isUpdate = true;
  }
 }
 
 if (mark){
  mapCopy();
  Bfs(i, j);
 }
 
 
 }
 }
 }
 return isUpdate;
}
bool bfsCheck(int x, int y, int squre){
 //bfs標(biāo)記及越界檢測
 if (x < 1 || x >= size || y < 1 || y >= size)return false;
 if (bfsVis[x][y] != 0 || Map[x][y] != squre)return false;
 return true;
}
void Bfs(int x, int y){
 int ans = 0;
 queue<node>S;
 node now, next;
 now.x = x, now.y = y;
 bfsVis[x][y] = 1;
 //point_vis[x][y] = 1;
 
 int squre = Map[x][y];
 
 Map[x][y] = -1;
 
 cout << "BFS: " << x << " " << y << endl;
 S.push(now);
 while (!S.empty()){
 now = S.front();
 ans++;
 S.pop();
 for (int i = 0; i < 4; i++){
 next = now;
 next.x += xx[i], next.y += yy[i];
 if (bfsCheck(next.x, next.y, squre) == 0)continue;
 bfsVis[next.x][next.y] = 1;
 
 Map[next.x][next.y] = -1;
 
 S.push(next);
 }
 }
 Score += ans;
 displayUpdate();
}
 
void displayUpdate(){
 //消失效果
 system("CLS");
 updateMap(1);
 Sleep(500);
 system("CLS");
 updateMap(2);
 Sleep(500);
 system("CLS");
 updateMap(1);
 Sleep(500);
 system("CLS");
 updateMap(2);
 Sleep(500);
 system("CLS");
 updateMap(1);
}
 
void dropNumberCount(){
 //下落高度統(tǒng)計
 for (int i = 1; i < size; i++){
 for (int j = 1; j < size; j++){
 if (Map[i][j] == -1){
 dropNumbe[i][j] = 0;
 continue;
 }
 int sum = 0;
 for (int z = i + 1; z < size; z++){
 if (Map[z][j] == -1)sum++;
 }
 dropNumbe[i][j] = sum;
 }
 }
}
 
void squreDrop(){
 //根據(jù)下落高度更新地圖
 for (int i = size - 1; i >= 1; i--){
 for (int j = 1; j < size; j++){
 int temp = dropNumbe[i][j];
 if (temp != 0){
 Map[i + temp][j] = Map[i][j];
 Map[i][j] = -1;
 }
 }
 }
}
 
void reflashMap(){
 //下落后的地圖新元素添加
 for (int i = 1; i < size; i++){
 for (int j = 1; j < size; j++){
 if (Map[i][j] == -1){
 Map[i][j] = (rand() % 4);
 }
 }
 }
}
 
void mapCopy(){
 //數(shù)組復(fù)制
 for (int i = 1; i < size; i++){
 for (int j = 1; j < size; j++){
 Map_2[i][j] = Map[i][j];
 }
 }
}