Ivelin Pavlov

ЗАДАЧА – Островландия

Известният мореплавател Станчо използвал своите хакерски умения и се сдобил с карта на Островландия. За съжаление обаче съкровището не било отбелязано с голям червен Х, ами просто било казано, че то се намира на най- големия остров. Картата била представена под формата на голям хексагон (правилен шестоъгълник), който е съставен от много на брой по малки хексагони. Страната на картата (големият хексагон) се състои от N хексагона. Всяка клетка в картата има стойност – нула или единица, в която нулите са вода, а единиците – суша. Съответно островите били съседни клетки от единици (като две клетки ще наричаме съседни, ако имат обща стена). Вашата задача е по дадена карта на Островландия да изведете големината на най- големия остров (в брой клетки). Най-големият остров на примера по-долу е отбелязан със зелени 1-ци.

Вход
От първия ред на стандартния вход програмата прочита едно число: 1 <= N <= 1000, представляващ броят на хексагоните стоящи на едната страна на картата. Следват 2 * N – 1 реда, всеки на който има последователности от нули и единици, описващи даден ред на картата.

Изход
На един ред на стандартния изход да се извежда едно число – големината на най-големия остров.

ПРИМЕРЕН ВХОД
5
1 0 0 1 1
1 0 1 0 1 0
1 0 0 0 1 0 1
1 0 0 0 1 1 1 0
0 1 0 1 1 0 0 1 1
0 0 0 0 0 1 1 0
1 1 0 0 0 0 0
1 1 0 1 1 0
1 0 1 0 1

ПРИМЕРЕН ИЗХОД
14

#include 
using namespace std;
bool island[2000][2000];
bool visitIsland[2000][2000];

int islandLength(int row, int col, int base) {
	visitIsland[row][col] = 1;
	int length = 1;
	if (row > 0) {
		if (row <= base-1) {
			if (col > 0) {
				if (row == base-1) {
					if (island[row+1][col-1] == 1 
						&& visitIsland[row+1][col-1] == 0) //dolu lqvo 1
						length += islandLength(row+1, col-1, base);
				}
				if (island[row-1][col-1] == 1 
					&& visitIsland[row-1][col-1] == 0) //gore lqvo
					length += islandLength(row-1, col-1, base);
				if (island[row][col-1] == 1 
					&& visitIsland[row][col-1] == 0) //lqvo 1
					length += islandLength(row, col-1, base);

			}
			if (col < base + row - 1) {
				if (row == base-1) {
					if(island[row+1][col] == 1 
						&& visitIsland[row+1][col] == 0) //dolu dqsno 1
						length += islandLength(row+1, col, base);
				}
				if (island[row-1][col] == 1 
					&& visitIsland[row-1][col] == 0) //gore dqsno
					length += islandLength(row-1, col, base);
				if (island[row][col+1] == 1 
					&& visitIsland[row][col+1] == 0) //dqsno 1
					length += islandLength(row, col+1, base);
			}
			if (row < base -1) {
				if (island[row+1][col] == 1 
					&& visitIsland[row+1][col] == 0) //dolu lqvo 2
					length += islandLength(row+1, col, base);
				if (island[row+1][col+1] == 1 
					&& visitIsland[row+1][col+1] == 0) //dolu dqsno 2
					length += islandLength(row+1, col+1, base);
			}
		} else {
			if (island[row-1][col] == 1 
				&& visitIsland[row-1][col] == 0) //gore lqvo 3
				length += islandLength(row-1, col, base);
			if (island[row-1][col+1] == 1 
				&& visitIsland[row-1][col+1] == 0) //gore dqsno 3
				length += islandLength(row-1, col+1, base);
			if (col < 3*base - row - 3) {
				if (row < 2*base - 1) {
					if (island[row+1][col] == 1 
						&& visitIsland[row+1][col] == 0) //dolu dqsno 2
						length += islandLength(row+1, col, base);
				}
				if (island[row][col+1] == 1 
					&& visitIsland[row][col+1] == 0) //dqsno 2
					length += islandLength(row, col+1, base);
			}
			if (col > 0) {
				if (row < 2*base - 1) {
					if (island[row+1][col-1] == 1 
						&& visitIsland[row+1][col-1] == 0) //dolu lqvo 3
						length += islandLength(row+1, col-1, base);
				}
				if (island[row][col-1] == 1 
					&& visitIsland[row][col-1] == 0) //lqvo 2
					length += islandLength(row, col-1, base);
			}
		}

	} else {
		if(col > 0) {
			if(island[row][col-1] == 1 
				&& visitIsland[row][col-1] == 0) //lqvo 3
				length += islandLength(row, col-1, base);
		}
		if(col < base + row - 1) {
			if(island[row][col+1] == 1
				&& visitIsland[row][col+1] == 0) //dqsno 3
				length += islandLength(row, col+1, base);
		}
		if (island[row+1][col] == 1 
			&& visitIsland[row+1][col] == 0) //dolu lqvo 3
			length += islandLength(row+1, col, base);
		if (island[row+1][col+1] == 1 
			&& visitIsland[row+1][col+1] == 0) //dolu dqsno 3
			length += islandLength(row+1, col+1, base);
	}
	return length;
}

int main() {
	int count;
	int lnLength;
	cin >> count;
	
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < count + i; j++) {
			cin >> island[i][j];
			visitIsland[i][j] = 0;
		}
	}
	for (int i = count; i < 2 * count - 1; i++) {
		for (int j = 0; j < 3 * count - i-2; j++) {
			cin >> island[i][j];
			visitIsland[i][j] = 0;
		}
	}


	int bigest = 0;
	int temp;
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < count + i; j++) {
			if (island[i][j] == 1 && visitIsland[i][j] == 0) {
				temp = islandLength(i,j,count);
				if (temp > bigest) {
					bigest = temp;
				}
			}

		}
	}
	for (int i = count; i < 2 * count - 1; i++) {
		for (int j = 0; j < 3 * count - i-2; j++) {
			if (island[i][j] == 1 && visitIsland[i][j] == 0) {
				temp = islandLength(i,j,count);
				if (temp > bigest) {
					bigest = temp;
				}
			}
		}
	}
	cout << bigest<