#include <allinc.h>
#define OMGLOLWTFBBQ 1337
//#define BOARD_ROWS 23
//#define BOARD_COLS 79
//#define BOMB_COUNT 200
#define DENY_NONZERO 1

int BOARD_ROWS;
int BOARD_COLS;
int BOMB_COUNT;

struct _tile
{
	int status;//0~8 number behind marker
	bool bomb;//1 = contains a bomb
   bool flagged;//1 = marked as a bomb
   bool hidden;//0 = uncovered, show STATUS
};

void initialize(apmatrix <_tile> &);
void plantbombs(apmatrix <_tile> &);
void showboard(apmatrix <_tile> &);
void getmove(apmatrix <_tile> &);
bool nextmove(apmatrix <_tile> &);
void clearzeroes(apmatrix <_tile> &);
void napalm(apmatrix <_tile> &, int, int);
void flagpalm(apmatrix <_tile> &, int, int);
int  countflags(apmatrix <_tile> &, int, int);
int  countunmarked(apmatrix <_tile> &, int, int);

void main()
{
	cout<<"ROWS: "; cin>>BOARD_ROWS;
	cout<<"COLS: "; cin>>BOARD_COLS;
   cout<<"BOMB: "; cin>>BOMB_COUNT;
   clrscr();

	bool repeat;
	randomize();
	apmatrix <_tile> board (BOARD_ROWS,BOARD_COLS);
   initialize(board);
   plantbombs(board);

	//make initial move
   getmove(board);
   showboard(board);
   //getch();
   clearzeroes(board);
   showboard(board);

   bool cleared;
   int x=1;
   do
   {
      x++;
   	//getch();

      //make next move
	   repeat=nextmove(board);
	   clearzeroes(board);
	   showboard(board);
      cout<<"Moves: "<<x;

      //check if cleared, if so, break loop
	   cleared=true;
	   for(int i=0; i<board.numrows(); i++)
	   for(int j=0; j<board.numcols(); j++)
	   	if(board[i][j].hidden && !board[i][j].flagged)
	      	cleared=false;

   }while(repeat && !cleared);
   if(!cleared)
	   cout<<"\nOut of moves...";
   else
   	cout<<"\nCLEARED!";
   getch();
}

void initialize(apmatrix <_tile> &board)
//Use: stores initial values into undefined values in each tile
//Args: board to be initialized, of type _tile
//Notes: status=0, bomb=0, flagged=0, hidden=1
{
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   {
   	board[i][j].status=0;
      board[i][j].bomb=0;
      board[i][j].flagged=0;
      board[i][j].hidden=1;
   }
}

void plantbombs(apmatrix <_tile> &board)
//Use: determine which positions are to have bombs, then mark off
//     status values of others
//Args: board to be planted, of type _tile
{
   //creates an indepent list of tile indices- 0 to ROW*COL-1
	apvector <int> tiles(board.numrows()*board.numcols());
   for(int i=0; i<tiles.length(); i++)
   	tiles[i]=i;

   //shuffles list, double swap-pass method
   for(int h=1; h<=2; h++)
   for(int i=0; i<tiles.length(); i++)
   {
   	int target=rand()%tiles.length();
      int temp=tiles[target];
      tiles[target]=tiles[i];
      tiles[i]=temp;
   }

   //assign bombs to indicies given starting at the front of tiles[]
   for(int i=0; i<BOMB_COUNT; i++)
    	if(i<tiles.length())//make sure there are no excess bombs
      {
      	int a=tiles[i];        //symbolic temps
         int r=board.numrows();
         int c=board.numcols();
         board[a/c][a%c].bomb=1; //set up us the bomb!

         //increment status numbers in legal adjacent squares
         if(0<=a/c-1 && 0<=a%c-1) board[a/c-1][a%c-1].status++;
         if(0<=a/c-1            ) board[a/c-1][a%c  ].status++;
         if(0<=a/c-1 && a%c+1< c) board[a/c-1][a%c+1].status++;
         if(            0<=a%c-1) board[a/c  ][a%c-1].status++;
         if(            a%c+1< c) board[a/c  ][a%c+1].status++;
         if(a/c+1< r && 0<=a%c-1) board[a/c+1][a%c-1].status++;
         if(a/c+1< r            ) board[a/c+1][a%c  ].status++;
         if(a/c+1< r && a%c+1< c) board[a/c+1][a%c+1].status++;
      }
      else
      {
      	cout<<"TOO MANY BOMBS!"; getch();
      }
}

void showboard(apmatrix <_tile> &board)
//Use: displays board so far.
{
	//clrscr();
   gotoxy(1,1);
	for(int i=0; i<board.numrows(); i++)
   {
   	for(int j=0; j<board.numcols(); j++)
         if(board[i][j].bomb && board[i][j].flagged)
           	cout<<"M";//marked bomb
         else if(!board[i][j].bomb && board[i][j].flagged)
         	cout<<"F";//false bomb
      	else if(board[i][j].hidden)
         	cout<<".";//hidden
         else if(board[i][j].bomb && !board[i][j].flagged)
           	cout<<"B";//bomb
         else
	      	cout<<board[i][j].status;//no bomb
      cout<<endl;
   }
}

void clearzeroes(apmatrix <_tile> &board)
//Use: "explodes" any zero tiles, like in the game. Automatically clears
//     all 3/5/8 blocks around a zero.
{
	bool repeat;//tells loop that it has found an exploded a zero, and to go
               //back around and check if that made any more zeroes.
	do
   {
   	repeat=false;
		for(int i=0; i<board.numrows(); i++)
	   for(int j=0; j<board.numcols(); j++)
	   	if(!board[i][j].hidden && board[i][j].status==0 && countunmarked(board,i,j)>0)
	      {//if spot is uncovered and shows a zero and has hidden tiles around it...
         	repeat=true; //repeat after checking
            napalm(board,i,j); //bomb it
	      }
   }while(repeat);
}

void napalm(apmatrix <_tile> &board, int i, int j)
//Use: Unhides all tiles in vicinity that are not marked.
//Args: board, and location to napalm
{
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   //check nearby positions and uncover them
   if(0<=a/c-1 && 0<=a%c-1) if(!board[a/c-1][a%c-1].flagged) {board[a/c-1][a%c-1].hidden=0;}
   if(0<=a/c-1            ) if(!board[a/c-1][a%c  ].flagged) {board[a/c-1][a%c  ].hidden=0;}
   if(0<=a/c-1 && a%c+1< c) if(!board[a/c-1][a%c+1].flagged) {board[a/c-1][a%c+1].hidden=0;}
   if(            0<=a%c-1) if(!board[a/c  ][a%c-1].flagged) {board[a/c  ][a%c-1].hidden=0;}
   if(            a%c+1< c) if(!board[a/c  ][a%c+1].flagged) {board[a/c  ][a%c+1].hidden=0;}
   if(a/c+1< r && 0<=a%c-1) if(!board[a/c+1][a%c-1].flagged) {board[a/c+1][a%c-1].hidden=0;}
   if(a/c+1< r            ) if(!board[a/c+1][a%c  ].flagged) {board[a/c+1][a%c  ].hidden=0;}
   if(a/c+1< r && a%c+1< c) if(!board[a/c+1][a%c+1].flagged) {board[a/c+1][a%c+1].hidden=0;}
}

void flagpalm(apmatrix <_tile> &board, int i, int j)
//Use: Flags all tiles in vicinity that are hidden
//Args: board, and location to flagpalm
{
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   //check nearby positions and uncover them
   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].hidden) {board[a/c-1][a%c-1].flagged=1;}
   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].hidden) {board[a/c-1][a%c  ].flagged=1;}
   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].hidden) {board[a/c-1][a%c+1].flagged=1;}
   if(            0<=a%c-1) if(board[a/c  ][a%c-1].hidden) {board[a/c  ][a%c-1].flagged=1;}
   if(            a%c+1< c) if(board[a/c  ][a%c+1].hidden) {board[a/c  ][a%c+1].flagged=1;}
   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].hidden) {board[a/c+1][a%c-1].flagged=1;}
   if(a/c+1< r            ) if(board[a/c+1][a%c  ].hidden) {board[a/c+1][a%c  ].flagged=1;}
   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].hidden) {board[a/c+1][a%c+1].flagged=1;}
}

void getmove(apmatrix <_tile> &board)
//Use: gets a move from the board. Preferrably an initial move...
//Args: the board
//Note: const-toggle controls whether or not this function finds a
//      zero-status tile or not. If not, it returns first non-bomb it finds
{

	//make a temporary bool array the same size as the normal board. Set to true.
   //when a tile is checked, negate the temp array value. Deny access if tile has already been checked
   //When sum of all temp tiles equals zero, ...break?

	int temp,i,j;
	do
   {
   	temp=rand()%(board.numcols()*board.numrows());
      i=temp/board.numcols();
      j=temp%board.numcols();
   }while(board[i][j].bomb || (board[i][j].status!=0 && DENY_NONZERO));
   board[i][j].hidden=0;
}

bool nextmove(apmatrix <_tile> &board)
//Use: sequentially checks each tile for potential moves.
{
	int unmarkedcount;
	for(int i=0; i<board.numrows(); i++)
   for(int j=0; j<board.numcols(); j++)
   	if(!board[i][j].hidden) //ignore tile if it's hidden
   	{
	   	unmarkedcount=countunmarked(board,i,j);
	      if(unmarkedcount>0) //ignore if there's nothing unmarked around it
         {
		   	int flagcount=countflags(board,i,j);
            if(flagcount+unmarkedcount==board[i][j].status && !board[i][j].bomb)
            {
            	flagpalm(board,i,j);
               return true;
            }
	         if(flagcount==board[i][j].status)
            {
            	napalm(board,i,j);
               return true;
            }
	      }
      }
   return false;
}

int countflags(apmatrix <_tile> &board, int i, int j)
//Use: counts marked bombs in nearby area
//Args: board, location around which to check
//Returns: number of flags in vicinity
{
	int markcount=0; //returned value
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].flagged) {markcount++;}
   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].flagged) {markcount++;}
   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].flagged) {markcount++;}
   if(            0<=a%c-1) if(board[a/c  ][a%c-1].flagged) {markcount++;}
   if(            a%c+1< c) if(board[a/c  ][a%c+1].flagged) {markcount++;}
   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].flagged) {markcount++;}
   if(a/c+1< r            ) if(board[a/c+1][a%c  ].flagged) {markcount++;}
   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].flagged) {markcount++;}
   return markcount;
}

int countunmarked(apmatrix <_tile> &board, int i, int j)
//Use: counts marked bombs in nearby area
//Args: board, location around which to check
//Returns: number of hidden, non-flagged tiles in vicinity
{
	int markcount=0; //returned value
  	int a;//temporary value for current position on board
   int r=board.numrows();
   int c=board.numcols();

  	a=i*c+j; //current location

   if(0<=a/c-1 && 0<=a%c-1) if(board[a/c-1][a%c-1].hidden && !board[a/c-1][a%c-1].flagged) {markcount++;}
   if(0<=a/c-1            ) if(board[a/c-1][a%c  ].hidden && !board[a/c-1][a%c  ].flagged) {markcount++;}
   if(0<=a/c-1 && a%c+1< c) if(board[a/c-1][a%c+1].hidden && !board[a/c-1][a%c+1].flagged) {markcount++;}
   if(            0<=a%c-1) if(board[a/c  ][a%c-1].hidden && !board[a/c  ][a%c-1].flagged) {markcount++;}
   if(            a%c+1< c) if(board[a/c  ][a%c+1].hidden && !board[a/c  ][a%c+1].flagged) {markcount++;}
   if(a/c+1< r && 0<=a%c-1) if(board[a/c+1][a%c-1].hidden && !board[a/c+1][a%c-1].flagged) {markcount++;}
   if(a/c+1< r            ) if(board[a/c+1][a%c  ].hidden && !board[a/c+1][a%c  ].flagged) {markcount++;}
   if(a/c+1< r && a%c+1< c) if(board[a/c+1][a%c+1].hidden && !board[a/c+1][a%c+1].flagged) {markcount++;}
   return markcount;
}