SRM198

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Div 2, Level 1

Div 2, Level 2

Div 2, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

BFS.

Source Code:

 //Fri Jun 17 17:34:14 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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;

#define mpp pair<int, pair<int, int> >
#define mp(a,b,c) make_pair(a, make_pair(b,c))
#define INF 200000000

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

int dist[60][60];

class DungeonEscape {
public:
    int exitTime(vector <string>, vector <string>, vector <string>, vector <string>, int, int);
};

int DungeonEscape::exitTime(vector <string> up, vector <string> down, vector <string> east, vector <string> west, int sl, int se) {
    int N = up.size();
    int M = up[0].size();
    for(int i=0; i<N; i++) for(int j=0; j<M; j++) dist[i][j] = INF;
 
    priority_queue<mpp> q;
    q.push(mp(0, sl, se));
    while(!q.empty()){
        int x = q.top().second.first;
        int y = q.top().second.second;
        int cost = -q.top().first;
        q.pop();
        if(x <= -1) return cost;
        if(dist[x][y] <= cost) continue;
        if(x>=N || y<0 || y>=M || cost>=(N-x)*M) continue;
        dist[x][y] = cost;
        for(int i=0; i<4; i++){
            int c;
            if(i==0) c=east[x][y];
            if(i==1) c=west[x][y];
            if(i==2) c=down[x][y];
            if(i==3) c=up[x][y];
            c -= 48;
            if(c<0 || c>9) continue;
            q.push(mp(-cost-c, x+dx[i], y+dy[i]));
        }
    }
    return -1;
}


//Powered by [KawigiEdit] 2.0!

Division One - Level One:

Solution

Source Code:

Division Two - Level Three:

Solution

Source Code:

Division Two - Level Two:

Solution

Source Code:

Division Two - Level One:

Solution

Source Code: