TCCC2003Round04

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Using DFS to implement DP;

PS: grid[x][y][rem] : # of ways to the location x, y with rem moves left.

Source Code:

//Mon Jun  6 15:02:54 CDT 2011
#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 <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

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

class ChessMetric {
public:
    long long howMany(int, vector <int>, vector <int>, int);
    long long dfs(int, int, int, int, int);
    bool checkBound(int x, int y);
    long long grid[101][101][51];
    int size;
};

long long ChessMetric::howMany(int sz, vector <int> start, vector <int> end, int numMoves) {
    size = sz;
    memset(grid, -1, sizeof(grid));
    return dfs(start[0], start[1], end[0], end[1], numMoves);
}

long long ChessMetric::dfs(int cx, int cy, int ex, int ey, int moves){
    if(moves ==0) return cx==ex && cy==ey;
    long long &ret = grid[cx][cy][moves];
    if(ret != -1) return ret;
    ret = 0;
    for(int i=0; i<16; i++){
        int xx = cx + dx[i];
        int yy = cy + dy[i];
        if(checkBound(xx, yy)){
            ret += dfs(xx, yy, ex, ey, moves-1);
        }
    }
    return ret;
}

bool ChessMetric::checkBound(int x, int y){
    return x>=0 && x<size && y>=0 && y<size;
}

<%:testing-code%>
//Powered by [KawigiEdit] 2.0!