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

/* ---- stack data-structure ---- */
struct pos {
	int row;
	int col;
	struct pos *next;
};

struct pos *head, *tail;

/* ---- operatioin of stack ---- */
void
init(void)
{
	head = tail = NULL;
}

void
push(int row, int col)
{
	struct pos *tmp = NULL;

	if (head == NULL && tail == NULL) {
		tmp = (struct pos*)malloc(sizeof(struct pos));
		if (tmp == NULL)
			exit(-1);
		tmp->row = row;
		tmp->col = col;
		head = tail = tmp;
	} else {
		tmp = (struct pos*)malloc(sizeof(struct pos));
		if (tmp == NULL)
			exit(-1);
		tmp->row = row;
		tmp->col = col;
		tmp->next = head;
		head = tmp;
	}
}

int
pop(int *row, int *col)
{
	struct pos *tmp = NULL;

	if (head == tail) {
		if (head == NULL)
			return 1;
		*row = head->row;
		*col = head->col;
		free(head);
		head = tail = NULL;
	} else {
		*row = head->row;
		*col = head->col;
		tmp = head;
		head = tmp->next;
		free(tmp);
	}
	return 0;
}

/* ---- main algorithm for dealing the problem ---- */
void
castle(int (*room)[70], int row, int col)
{
	int flag[50][50] = {};	// array of flags for deciding which cell is accessed, which one is not
	int i, j, cur_row, cur_col, cell;
	int cnt, cnt_cell, ret, max;
	// this two variable is just for debugging ---- int m, n;
	
	init();					// initialize the stack data-structure
	cnt = 0;				// number of rooms
	cnt_cell = 0;			// count of cells of one room
	max = 0;				// the number of cells which the largest room has
	cur_row = cur_col = 0;
	cell = 0;
	ret = 0;

	for (i = 0;i < row;i++)
		for (j = 0;j < col;j++) {
			if (flag[i][j] == 0) {
				push(i,j);
				cnt_cell++;
				flag[i][j] = 1;
				cur_row = i;
				cur_col = j;
				while (1) {
					cell = room[cur_row][cur_col];
					if (!(cell&1)) {
						push(cur_row,cur_col-1);
						if (flag[cur_row][cur_col-1] == 0)
							cnt_cell++;
						flag[cur_row][cur_col-1] = 1;
						room[cur_row][cur_col] |= 1;
						cur_col = cur_col - 1;
						room[cur_row][cur_col] |= 4;
					} else if (!(cell&2)) {
						push(cur_row-1,cur_col);
						if (flag[cur_row-1][cur_col] == 0)
							cnt_cell++;
						flag[cur_row-1][cur_col] = 1;
						room[cur_row][cur_col] |= 2;
						cur_row = cur_row - 1;
						room[cur_row][cur_col] |= 8;
					} else if (!(cell&4)) {
						push(cur_row,cur_col+1);
						if (flag[cur_row][cur_col+1] == 0)
							cnt_cell++;
						flag[cur_row][cur_col+1] = 1;
						room[cur_row][cur_col] |= 4;
						cur_col = cur_col + 1;
						room[cur_row][cur_col] |= 1;
					} else if (!(cell&8)) {
						push(cur_row+1,cur_col);
						if (flag[cur_row+1][cur_col] == 0)
							cnt_cell++;
						flag[cur_row+1][cur_col] = 1;
						room[cur_row][cur_col] |= 8;
						cur_row = cur_row + 1;
						room[cur_row][cur_col] |= 2;
					} else {
						ret = pop(&cur_row,&cur_col);
						if (ret != 0)
							break;
					}
				} //end of while
				if (cnt_cell > max)
					max = cnt_cell;
				cnt_cell = 0;
				cnt++;
				/* this is for debugging, to print the status of every cell
				for (m = 0;m < row;m++) {
					for (n = 0;n < col;n++)
						printf("%d ",flag[m][n]);
					printf("\n");
				}
				
				printf("\n");
				*/
			} // end of if
		} // end of second for

	printf("%d\n",cnt);
	printf("%d\n",max);

	return;
}


int
main(void)
{
	int row, col, i, j, val;
	int room[70][70] = {};
	
	scanf("%d",&row);
	scanf("%d",&col);

	if (row < 0 || row > 50 || col < 0 || col > 50)
		exit(-1);

	for (i = 0;i < row;i++) {
		for (j = 0;j < col;j++) {
			scanf("%d",&val);
			if (val < 0 || val > 15)
				exit(-1);
			room[i][j] = val;
		}
	}

	castle(room,row,col);

/* just for print the array
	for (i = 0;i < row;i++) {
		for (j = 0;j < col; j++)
			printf("%d ",room[i][j]);
		printf("\n");
	}
*/
	return 0;
}

• Re:WA好多次了，郁闷啊。试了变量赋初值，数组开大一点，希望大家帮忙，附丑陋代码。 (4345) ocelot1985 2011-08-16 22:16:40