OJ Board

Code: Select all

Removed After AC :)

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int m, n, x, y, i, j, k;
int parent[10005];
char s[105][105];

int sum[10005];

int ans;

int dirx[] = {0,0,1,-1};
int diry[] = {1,-1,0,0};

char LAND;

int getid(int a, int b)
{
	return a * m + b;
}

int getparent(int a)
{
	return (parent[a] == a)? a : (parent[a] = getparent(parent[a]));
}

void unionset(int a, int b)
{
	parent[getparent(a)] = getparent(b);
}


int main()
{
	while (scanf("%d %d", &m, &n) != EOF)
	{
		for (i = 0; i < m; ++i)
			scanf("%s", s[i]);
		
		scanf("%d %d", &x, &y);
		
		LAND = s[x][y];
		
		// reset parent
		for (i = 0; i < m; ++i)
			for (j = 0; j < n; ++j)
			{	
				int id = getid(i,j);
				
				parent[id] = id;
			}
		
		// union parents
		for (i = 0; i < m; ++i)
		{
			for (j = 0; j < n; ++j)
			{
				if (s[i][j] != LAND) continue;
				
				int id = getid(i,j);
				
				for (k = 0; k < 4; ++k)
				{
					int nx = i+dirx[k], ny = (j+diry[k])%n;
										
					if (nx >= 0 && nx < m)
					{
						if (s[nx][ny] == LAND)
						{
							unionset(id, getid(nx,ny));
						}
					}
				}
			}
		}
		
		// count continents
		memset(sum, 0, sizeof(sum));
		for (i = 0; i < m; ++i)
			for (j = 0; j < n; ++j)
			{
				if (s[i][j] == LAND) sum[getparent(getid(i,j))]++;
			}
				
		// find answer
		ans = 0;
		for (i = 0; i < m; ++i)
		{
			for (j = 0; j < n; ++j)
			{				
				if (s[i][j] == LAND)
				if (getparent(getid(i,j)) != getparent(getid(x,y)))
					ans = max(ans, sum[getparent(getid(i,j))]);
			}
		}
		
		printf("%d\n", ans);
	}
	return 0;
}

Code: Select all

#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;
char M[25][25];
bool Visit[25][25];

typedef stack<int> Si;
int m,n;
int cont;
char land,water;

void FirstDFS(int first,int second)
{
	if(second>=n)
		second = 0;
	if(second<0)
		second = n-1;
	if(first>=m || first<0)
		return;
	if(M[first][second]!=land)
		return;

	M[first][second]=water;

	FirstDFS(first+1,second);
	FirstDFS(first-1,second);
	FirstDFS(first,second-1);
	FirstDFS(first,second+1);

}

void SecondDFS(int first,int second)
{
	if(second>=n)
		second = 0;
	if(second<0)
		second = n-1;
	if(first>=m || first<0)
		return;
	if(M[first][second]!=land)
		return;

	M[first][second]=water;
	cont++;

	SecondDFS(first,second-1);
	SecondDFS(first,second+1);
	SecondDFS(first+1,second);
	SecondDFS(first-1,second);
}


int main()
{
	int x,y;
    while(scanf("%d %d\n",&m,&n)==2)
	{
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf(" %c",&M[i][j]);
			}
		}
		

		scanf("%d %d\n\n",&x,&y);
		land = M[x][y];
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if(M[i][j]!=land)
					water = M[i][j];
			}
		}


		FirstDFS(x,y);
		int max=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(M[i][j]!=water)
				{
					cont=0;
					SecondDFS(i,j);
					if(cont>max)
						max=cont;
				}
				
			}		
		}
		printf("%d\n",max);
	}
    return 0;
}

Code: Select all

3 3
l--
---
---
0 0

3 3
---
---
---
0 0

Code: Select all

Removed

Code: Select all

Accepted... :)