Topcoder SRM576 Div2

ArcadeManao.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define inf		2000

using namespace std;

class ArcadeManao {
public:
	int shortestLadder(vector <string>, int, int);
};

bool Map[51][51];

int part[51][51];

bool flag[51][51];

int partno;

int dist[1300][1300];

void dfs(int x, int y)
{
	flag[x][y] = false;
	part[x][y] = partno;
	if (flag[x][y + 1] && Map[x][y + 1]) dfs(x, y + 1);	
}

bool reach[1300];

int limit;

void walk(int x)
{
	reach[x] = true;
	for (int i = 0; i < partno; ++ i)
		if (!reach[i] && dist[x][i] <= limit)
			walk(i);
}

bool check(int source, int target)
{
	memset(reach, false, sizeof(reach));
	walk(source);
	return reach[target];
}

int ArcadeManao::shortestLadder(vector <string> level, int coinRow, int coinColumn) {
	int n = level.size();
	int m = level[0].length();

	memset(Map, false, sizeof(Map));
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < m; ++ j)
			Map[i][j] = (level[i][j] == 'X');

	partno = 0;
	memset(flag, true, sizeof(flag));
	memset(part, -1, sizeof(part));
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < m; ++ j)
			if (flag[i][j] && Map[i][j])
			{
				dfs(i, j);
				++ partno;
			}

	for (int i = 0; i < partno; ++ i)
	{
		dist[i][i] = 0;
		for (int j = i + 1 ; j < partno; ++ j)
			dist[i][j] = dist[j][i] = inf;
	}

	
	for (int i = 0; i < n - 1; ++ i)
		for (int j = 0; j < m; ++ j)
			if (Map[i][j])
			{
				for (int k = i + 1; k < n; ++ k)
					if (Map[k][j])
						dist[part[k][j]][part[i][j]] = dist[part[i][j]][part[k][j]] = min(dist[part[i][j]][part[k][j]], abs(i - k));
			}

	for (limit = 0; limit <= n; ++ limit)
		if (check(part[n - 1][0], part[coinRow - 1][coinColumn - 1]))
			break;
	return limit;
}

CharacterBoard2.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class CharacterBoard2 {
public:
	int countGenerators(vector <string>, int, int, int);
};

char generator[10010];

const int MOD = 1000000009;

int CharacterBoard2::countGenerators(vector <string> fragment, int W, int i0, int j0) {
			
	long long ret = 0;

	int n = fragment.size();
	int m = fragment[0].length();

	for (int len = 1; len <= W; ++ len)
	{
		for (int i = 0; i < len; ++ i)
			generator[i] = '.';
		
		bool check = true;
		for (int i = 0; i < n; ++ i)
		{
			for (int j = 0; j < m; ++ j)
			{
				int pos = ((i + i0) * W + (j + j0)) % len;
				if (generator[pos] != '.' && generator[pos] != fragment[i][j])
				{
					check = false;
					break;
				}
				generator[pos] = fragment[i][j];	
			}
			if (!check) break;
		}
		if (!check) continue;
		long long k = 1;
		for (int i = 0; i < len; ++ i)
			if (generator[i] == '.')
				k = (k * 26) % MOD;
		ret = (ret + k) % MOD;
	}
	return (int)ret;
}

TheExperimentDiv2.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class TheExperimentDiv2 {
public:
	vector <int> determineHumidity(vector <int>, int, vector <int>);
};

vector <int> TheExperimentDiv2::determineHumidity(vector <int> intensity, int L, vector <int> leftEnd) {
	int m = leftEnd.size();

	vector <int> ret;
	ret.clear();

	for (int i = 0; i < m; ++ i)
	{
		int cur = 0;
		for (int j = leftEnd[i]; j < leftEnd[i] + L; ++ j)
		{
			cur += intensity[j];
			intensity[j] = 0;
		}
		ret.push_back(cur);
	}
	return ret;	
}