JOI2008-2009をC++で解いてみた4問目

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdlib.h>

using namespace std;

void outHistory(vector<int>* history_){
    vector<int>::iterator iter;
    for(iter=history_->begin(); history_->end() != iter; iter++){
        cout << *iter << "<";
    }
    cout << endl;
}

class Field{
    private:
        vector<bool> m_fieldline;
        int m_width, m_height;
        int m_movement[4];
    public:
        Field(ifstream* ifs){
            read(ifs);
            m_movement[0] = -1;
            m_movement[1] = -m_width;
            m_movement[2] = 1;
            m_movement[3] = m_width;
        }
        void read(ifstream* ifs){
            string buf;
            int numline = 0;
            while(getline(*ifs, buf)){
                numline++;
                if(numline == 1){
                    m_width = atoi(buf.c_str());
                }else if(numline == 2){
                    m_height = atoi(buf.c_str());
                }else{
                    string::iterator iter;
                    string temp = "";
                    buf.append(" ");
                    for(iter=buf.begin(); iter != buf.end(); iter++){
                        if(*iter == ' '){
                            m_fieldline.push_back(atoi(temp.c_str()));
                            temp.clear();
                        }else{
                            temp.append(1, *iter);
                        }
                    }
                }
            }
        }
        bool operator()(int x_, int y_){
            return m_fieldline[y_*m_width + x_];
        }
        const bool operator()(int x_, int y_) const{
            return m_fieldline[y_*m_width + x_];
        }
        int start(){
            vector<int> steps;
            vector<int> empty;
            for(int i=0; i < m_width*m_height; i++){
                if(m_fieldline[i] == true){
                    steps.push_back(walk(i, empty));
                }
            }
            return *(max_element(steps.begin(), steps.end()));
        }

        int walk(int pos, vector<int> history_){
            int candidates[4] = {0, 0, 0, 0};
            history_.push_back(pos);
            int invcnt = 0;
            bool ropes[5];
            for(int i=0; i < 4; i++){
                candidates[i] = pos + m_movement[i];
                ropes[0] = candidates[0]/m_width == pos/m_width;
                ropes[1] = candidates[2]/m_width == pos/m_width;
                ropes[2] = !(0 <= candidates[i] and candidates[i] < m_width*m_height);
                ropes[3] = count(history_.begin(), history_.end(), candidates[i]) != 0;
                ropes[4] = m_fieldline[candidates[i]] == false;
                if((i == 0 && ropes[0]) || (i == 2 && ropes[1]) || (i == 1) || (i == 3)){
                    if(ropes[2] || ropes[3] || ropes[4]){
                        candidates[i] = -1; //invalid position
                        invcnt++;
                    }
                }else{
                    candidates[i] = -1; //invalid position
                    invcnt++;
                }

            }
            outHistory(&history_);
            if(invcnt == 4){
                return history_.size();
            }else{
                vector<int> steps;
                for(int i=0; i < 4; i++){
                    if(candidates[i] != -1){
                        steps.push_back(walk(candidates[i], history_));
                    }
                }
                return *(max_element(steps.begin(), steps.end()));
            }
            return -1;
        }
};

int main(int argc, char* argv[]){
    ifstream ifs(argv[1]);
    Field* f = new Field(&ifs);
    int result;
    result = f->start();
    cout << result << endl;
    ofstream ofs(string(string(argv[1]) + string("_out.txt")).c_str());
    ofs << result << endl;
    delete f;
    f = 0;
    return 0;
}

実行してみるとハカーっぽくて楽しい。まぁごみで実行速度落とすだけだけど。
このくらいになると露骨にPythonとの速度差が出てくる。
SWIG使えばよかったのか？

三問目を飛ばしたのは、かけなかったから。後で書く。