UVA: 10189 Programming Challenges (Skiena & Revilla) Volume-1

UVA:10189:Minesweeper

Background- This is very cute easy game Minesweeper, The problem here is to reveal the step on mines. It was quite a fun coding this problem and has given me a good refresh to STL c++ library. With my favorite  coding environment STL the source size is quite small and got amazing 0.012 sec timing with this implementation. Whatever rest I tried gave me time overhead. My implementations are as follows -  


Now I have Version-2 which has slightly improved performance of 0.008 sec. There is slight change in implementation, actually I am not happy with my first try. It looks like I have not given enough time on implementation, It was mistake and want to keep here so that It can remind me every time I come here.

C++ Implementation:

version -2

#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
using namespace std;
void algorithm(string& prev, string& curr, string& res) {
    short m = curr.size()-2;
    string next(m+2, '0');
    size_t pos = 1;
    while(pos <= m) {
        if(curr[pos] == '*') {
                curr[pos+1] != '*' ? curr[pos+1] = 1 + res[pos+1]   : 0;
                curr[pos-1] != '*' ? curr[pos-1]++                  : 0;
                prev[pos]   != '*' ? prev[pos]++                    : 0;
                prev[pos+1] != '*' ? prev[pos+1]++                  : 0;
                prev[pos-1] != '*' ? prev[pos-1]++                  : 0;
                next[pos]++;
                next[pos+1]++;
                next[pos-1]++;
        } else if(curr[pos] == '.'){
            curr[pos] = res[pos];
        }
        pos++;
    }
    res = next;
}

/* main
 * */

int main() {
    long fields = 0;
    string curr;
    string prev;
    string res;
    curr.reserve(120);
    prev.reserve(120);
    res.reserve(120);
    while ( true ) {
        unsigned long n =0;
        unsigned long m =0;
        cin >> n >> m;
        if (n == 0 && m == 0) { 
            return 0;
        }
        prev= string(m+2, '0');
        res = string(m+2, '0');
        if(fields != 0) 
            cout << endl;
        fields++;
        cout << "Field #" << fields <<":" << endl;
        cin >> curr;
        curr = '0'+curr+'0';
        algorithm(prev, curr, res);
        prev = curr;
        for (short i = 1; i < n; i++) {
            cin >> curr;
            curr = '0'+curr+'0';
            algorithm(prev, curr, res);
            copy(prev.begin()+1, prev.begin()+m+1, ostream_iterator<char>(cout, ""));
            cout << endl;
            prev = curr;
        }
        copy(prev.begin()+1, prev.begin()+m+1, ostream_iterator<char>(cout, ""));
        cout << endl;
    }
}

version -1

Version - 1

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
ostringstream oss;
void algorithm(string& prev, string& curr, string& res) {
    short m = curr.size();
    string next(m, '0');
    size_t pos = 0;
    while(pos < m) {
        if(curr[pos] == '*') {
            if(pos == 0) {
                curr[pos+1] != '*' ? curr[pos+1]=1 + res[pos+1]     : 0;
                prev[pos]   != '*' ? prev[pos]++                    : 0;
                prev[pos+1] != '*' ? prev[pos+1]++                  : 0;
                next[pos]++;
                next[pos+1]++;
            } else if(pos == curr.size()-1) {
                curr[pos-1] != '*' ? curr[pos-1]++                    : 0;
                prev[pos]   != '*' ? prev[pos]++                    : 0;
                prev[pos-1] != '*' ? prev[pos-1]++                  : 0;
                next[pos]++;
                next[pos-1]++;
            } else {
                curr[pos+1] != '*' ? curr[pos+1]=1  + res[pos+1]    : 0;
                curr[pos-1] != '*' ? curr[pos-1]++                    : 0;
                prev[pos]   != '*' ? prev[pos]++                    : 0;
                prev[pos+1] != '*' ? prev[pos+1]++                  : 0;
                prev[pos-1] != '*' ? prev[pos-1]++                  : 0;
                next[pos]++;
                next[pos+1]++;
                next[pos-1]++;
            }
        } else if(curr[pos] == '.'){
            curr[pos] = res[pos];
        } else {
        }
        pos++;
    }
    res = next;
}

/* main
 * */

int main() {
    long fields = 0;
    string curr;
    string prev;
    string res;
    curr.reserve(120);
    prev.reserve(120);
    res.reserve(120);
    while ( true ) {
        unsigned long n =0;
        unsigned long m =0;
        cin >> n >> m;
        if (n == 0 && m == 0) { 
            cout << oss.str();
            return 0;
        }
        prev= string().append(m, '0');
        res = string().append(m, '0');
        if(fields != 0) 
            oss << endl;
        fields++;
        oss << "Field #" << fields <<":" << endl;
        for (short i = 0; i < n; i++) {
            cin >> curr;
            algorithm(prev, curr, res);
            if(i > 0)
                oss << prev << endl;
            prev = curr;
        }
        oss << prev << endl;
    }
}

Give a try and do share-