TCO2003Semifinal04

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

DFS to implement DP;

PS: 1st, the path is bi-direction, so does impassable path.

       2nd, Take care of the dimension, they are different than usual.

grid[x][y][num]: the different ways to the block located at x, y with num moves left.

Source Code:

//Mon Jun  6 15:52:14 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, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

class AvoidRoads {
public:
    long long numWays(int, int, vector <string>);
    long long dfs(int, int, int, int, int);
    bool checkBound(int, int);
    long long grid[102][102][205];
    map<pair<pair<int, int>, pair<int, int> >, bool> badlist;
    int w;
    int h;
};

long long AvoidRoads::numWays(int width, int height, vector <string> bad) {
    w = width;
    h = height;
    memset(grid, -1, sizeof(grid));
    int x1, y1, x2, y2;
    for(int i=0; i<bad.size(); i++){
        stringstream s(bad[i]);
        s >> y1 >> x1 >> y2 >> x2;
        badlist[make_pair(make_pair(x1, y1),make_pair(x2, y2))] = true;
        badlist[make_pair(make_pair(x2, y2),make_pair(x1, y1))] = true;
    }
    return dfs(0, 0, height, width, width + height);
}

long long AvoidRoads::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<4; i++){
        int xx = cx + dx[i];
        int yy = cy + dy[i];
        if(checkBound(xx, yy) && !badlist[make_pair(make_pair(cx, cy), make_pair(xx, yy))]){
            ret += dfs(xx, yy, ex, ey, moves-1);
        }
    }
    return ret;
}

bool AvoidRoads::checkBound(int x, int y){
    return (x>=0 && x<=h && y>=0 && y<=w);
}

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