TCCC2004 Online Round 04

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:

//Sun Jun 12 23:58:56 CDT 2011
#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>

using namespace std;

typedef pair <pair<int, int>, pair<int, int> > State;
#define mp(a,b,c,d) make_pair(make_pair(a,b),make_pair(c,d))

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

class BombMan {
public:
    bool checkBound(int x, int y){
        return x>=0 && x<M && y>=0 && y<N;
    }
    int shortestPath(vector <string>, int);
    int grid[51][51][101];
    int M;
    int N;
};

int BombMan::shortestPath(vector <string> maze, int bombs) {
    M = maze.size();
    N = maze[0].size();
    memset(grid, -1, sizeof(grid));
    priority_queue<State> q;
    for(int i=0; i<M; i++)
        for(int j=0; j<N; j++){
            if(maze[i][j]=='B'){
                q.push(mp(0, bombs, i, j));
                grid[i][j][bombs] = 0;
            }
        }
    while(!q.empty()){
        State tmp = q.top();
        q.pop();
        int cost = -tmp.first.first;
        int b = tmp.first.second;
        int x = tmp.second.first;
        int y = tmp.second.second;
        if(grid[x][y][b] < cost) continue;
        if(maze[x][y] == 'E') return cost;
       
        for(int i=0; i<4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(!checkBound(xx, yy)) continue;
            if(maze[xx][yy]!='#' && (grid[xx][yy][b] > cost + 1 || grid[xx][yy][b] == -1)){
                grid[xx][yy][b] = cost + 1;
                q.push(mp(-cost-1, b, xx, yy));
            }
            if(maze[xx][yy]=='#' && (grid[xx][yy][b-1] > cost + 3 || grid[xx][yy][b-1] == -1) && b>0){
                grid[xx][yy][b-1] = cost + 3;
                q.push(mp(-cost-3, b-1, xx, yy));
            }
        }
    }
    return -1;
}

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

Division One - Level One:

Solution

After viewing tons of red coders' code, I found I could not understand their code very smoothly. At last, I took this method to implement my code, though it's kind of DP, it still cost a lot of time. At least, I can understand. Hope I can be at that level some day, some time.

Source Code:

//Tue Jun  7 14:05:17 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;

class BadNeighbors {
public:
    int maxDonations(vector <int>);
};

int BadNeighbors::maxDonations(vector <int> dos) {
    int N = dos.size();
    int ret = 0;
    for(int i=0; i<N; i++){
        vector<int> cost(N, 0);
        cost[0] = dos[0];
        cost[1] = dos[1];
        ret = max(ret, cost[0]);
        ret = max(ret, cost[1]);
        for(int j=2; j<N-1; j++){
            cost[j] = max(cost[j-1], cost[j-2] + dos[j]);
            ret = max(ret, cost[j]);
        }
     
        rotate(dos.begin(), dos.begin() + 1, dos.end());
    }
    return ret;
}


//Powered by [KawigiEdit] 2.0!