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!
No comments :
Post a Comment