// Data Structure 2007 program assignment 1
// p96, 97 qestion 9
// compute random walk problem
// programmed by Davidson Chen (³¯«G¦t) 9565810
// 23 April 2007

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define max_row 20
#define max_col 40
#define min_row 2
#define min_col 3
#define max_iter_count 50000
#define out_file_name "9565810.csv"

int main(int argc, char** argv)
{
	//-----------------------------------------------------------------------------------
	//		variable declarations
	//-----------------------------------------------------------------------------------
	int i, j;					// loop indices
	int m, n;					// map = m by n matrix
	int ibug, jbug;				// bug's current position
	int unvisited;				// number of unvisited squares
	int iterCount = 0;			// iteration count
	int totalMoves = 0;			// total legal moves
	int imove[8], jmove[8];		// moving direction arrays
	int k;						// current moving direction (0~7)
	int map[max_row][max_col];	// maze
	FILE *fpOut;				// output file

	//-----------------------------------------------------------------------------------
	//		initialization
	//-----------------------------------------------------------------------------------

	// checking for the number of input arguments
	if (argc != 5){
		printf("Usage: 9565810.exe m n start_i start_j\n");
		printf("the map is initialized as an m by n matrix\n");
		printf("where %d<=n<=%d, %d<=m<=%d\n", min_col, max_col, min_row, max_row);
		printf("starting position = (start_i, start_j\n");
		exit(-1);
	}

	// retrieve inputs
	m = atoi(argv[1]);
	n = atoi(argv[2]);
	ibug = atoi(argv[3]);
	jbug = atoi(argv[4]);

	// map size and starting position check
	if ((m < min_row) || (m > max_row)){
		fprintf(stderr, "ERROR: illegal row size = %d!\n", m);
		fprintf(stderr, "Allowed row size is from %d to %d\n", min_row, max_row);
		exit(-1);
	}
	if ((n < min_col) || (n > max_col)){
		fprintf(stderr, "ERROR: illegal colume size = %d!\n", m);
		fprintf(stderr, "Allowed colume size is from %d to %d\n", min_col, max_col);
		exit(-1);
	}
	if ((ibug < 0) || (ibug >= m)){
		fprintf(stderr, "ERROR: illegal starting row position = %d!\n", ibug);
		fprintf(stderr, "starting row position must be within the range between 0 to %d\n", m-1);
		exit(-1);
	}
	if ((jbug < 0) || (jbug >= n)){
		fprintf(stderr, "ERROR: illegal starting colume position = %d!\n", jbug);
		fprintf(stderr, "starting colume position must be within the range between 0 to %d\n", n-1);
		exit(-1);
	}

	// initialize map matrix
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			map[i][j] = 0;

	//-----------------------------------------------------------------------------------
	//		random walk computation
	//-----------------------------------------------------------------------------------

	// place the bug onto the starting position
	map[ibug][jbug] = 1;
	unvisited = m * n - 1;

	// initialize random seed here
	srand(time(0));

	// initialize direction arrays
	imove[0] = -1;
	imove[1] = 0;
	imove[2] = 1;
	imove[3] = 1;
	imove[4] = 1;
	imove[5] = 0;
	imove[6] = -1;
	imove[7] = -1;

	jmove[0] = 1;
	jmove[1] = 1;
	jmove[2] = 1;
	jmove[3] = 0;
	jmove[4] = -1;
	jmove[5] = -1;
	jmove[6] = -1;
	jmove[7] = 0;

	// start iteration here...
	while ((unvisited > 0) && (iterCount <= max_iter_count))
	{
		iterCount++;

		// generat new move here
		k = rand() % 8;
		ibug += imove[k];
		jbug += jmove[k];
		while ((ibug < 0) || (ibug >= m) || (jbug < 0) || (jbug >= n)){
			ibug -= imove[k]; // restore old position
			jbug -= jmove[k]; // restore old position
			k = rand() % 8; // select a new moving direction
			ibug += imove[k];
			jbug += jmove[k];
		}

		// found moving direction, do necessary computation
		if (map[ibug][jbug] == 0)
			unvisited--;
		map[ibug][jbug]++;
	}

	//-----------------------------------------------------------------------------------
	//		output results
	//-----------------------------------------------------------------------------------

	// open file for output
	if ((fpOut = fopen(out_file_name, "wt"))==NULL){
		fprintf(stderr, "ERROR: fail to write to %s\n", out_file_name);
		exit(-1);
	}

	// output total number of legal moves
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			totalMoves += map[i][j];
	fprintf(fpOut, "Total number of legal moves: %d\n", totalMoves);

	// output map matrix
	for (i = 0; i < m; i++){
		for (j = 0; j < n; j++)
			fprintf(fpOut, "%d,", map[i][j]);
		fprintf(fpOut, "\n");
	}

	fclose(fpOut);

	return 0;
}
