Topcoder SRM590 Div2

FoxAndGo.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 <cstring>
#include <cstdlib>
#include <ctime>

using namespace std;

class FoxAndGo {
public:
	int maxKill(vector <string>);
};

int flag[20][20];

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int N;

void dfs(const vector<string> &a, int x, int y)
{
    flag[x][y] = 1;
    for (int i = 0; i < 4; ++ i)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 0 && xx < N && yy >= 0 && yy < N)
            if (flag[xx][yy] == 0 && (a[xx][yy] == '.' || a[xx][yy] == 'o'))
                    dfs(a, xx, yy);
    }
}


int checking(const vector<string> &a)
{
    memset(flag, 0, sizeof(flag));
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
        {
            if (a[i][j] == 'x')
                flag[i][j] = 1;
            else if (flag[i][j] == 0 && a[i][j] == '.')
                dfs(a, i, j);
        }
    int ret = 0;
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            if (flag[i][j] == 0) ++ ret;
    return ret;
}

int FoxAndGo::maxKill(vector <string> board) {
    N = board[0].size();
    int ans = 0;
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            if (board[i][j] == '.')
            {
                board[i][j] = 'x';
                ans = max(ans, checking(board));
                board[i][j] = '.';
            }
    return ans;
}

FoxAndGomoku.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 FoxAndGomoku {
public:
	string win(vector <string>);
};

string FoxAndGomoku::win(vector <string> board) {

    int N = board[0].size();

    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
        {
            if (board[i][j] == '.') continue;
            bool flag;
            if (i + 4 < N)
            {
                flag = true;
                if (board[i + 1][j] == '.') flag = false;
                if (board[i + 2][j] == '.') flag = false;
                if (board[i + 3][j] == '.') flag = false;
                if (board[i + 4][j] == '.') flag = false;
                if (flag) return "found";
            }
            if (j + 4 < N)
            {
                flag = true;
                if (board[i][j + 1] == '.') flag = false;
                if (board[i][j + 2] == '.') flag = false;
                if (board[i][j + 3] == '.') flag = false;
                if (board[i][j + 4] == '.') flag = false;
                if (flag) return "found";
            }
            if (i + 4 < N && j + 4 < N)
            {
                flag = true;
                if (board[i + 1][j + 1] == '.') flag = false;
                if (board[i + 2][j + 2] == '.') flag = false;
                if (board[i + 3][j + 3] == '.') flag = false;
                if (board[i + 4][j + 4] == '.') flag = false;
                if (flag) return "found";
            }
            if (i + 4 < N && j - 4 >= 0)
            {
                flag = true;
                if (board[i + 1][j - 1] == '.') flag = false;
                if (board[i + 2][j - 2] == '.') flag = false;
                if (board[i + 3][j - 3] == '.') flag = false;
                if (board[i + 4][j - 4] == '.') flag = false;
                if (flag) return "found";
            }
        }
    return "not found";
}

FoxAndShogi.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>
#include <cstring>

using namespace std;

const long long MOD = 1000000007LL;

class FoxAndShogi {
public:
	int differentOutcomes(vector <string>);
};

const int limitsize = 50;

long long dp(int N, const string &X)
{
    vector< pair<int, int> > line;
    int f[limitsize][limitsize];

    memset(f, 0, sizeof(f));
    line.clear();

    for (int i = 0; i < N; ++ i)
        if (X[i] == 'U')
            line.push_back(make_pair(i, -1));
        else if (X[i] == 'D')
            line.push_back(make_pair(i, 1));

    if (line.size() == 0) return 1;

    for (int i = line[0].first; i >= 0 && i < N; i += line[0].second)
        f[0][i] = 1;

    for (int i = 1; i < line.size(); ++ i)
        for (int j = line[i].first; j >= 0 && j < N; j += line[i].second)
            for (int k = 0; k < j; ++ k)
                f[i][j] = (f[i][j] + f[i - 1][k]) % MOD;

    long long ret = 0;
    for (int i = 0; i < N; ++ i)
        ret = (ret + f[line.size() - 1][i]) % MOD;

    return ret;
}

int FoxAndShogi::differentOutcomes(vector <string> board) {
    int N = board[0].size();

    long long ans = 1;

    string line;

    for (int i = 0; i < N; ++ i)
    {
        line = "";
        for (int j = 0; j < N; ++ j)
            line += board[j][i];
        ans = (ans * dp(N, line)) % MOD;
    }
    return (int)ans;
}