Marathon Match 78 FixTheFence

問題概要

Problem Statement

スリザーリンクのスコアアタック版。
スリザーリンクのルールに従い、出来る限り多くのセルの条件を満たす。

wikipedia:スリザーリンク

結果

90/105位
Rate:なし→1005

自分のアルゴリズム

時間ギリギリまで初期位置を適当に選択し、0の周囲を回避しつつ深さ優先探索でルートを探す。
複数のものが見つかったら得点で比較。
ループが作れなかったらあらかじめ用意したルートを出力。

感想

前回は不参加に近かったため、今回が実質的に初参戦。
自分の作ったプログラムが予想通り動いたり、ヴィジュアライザで視覚化されるのがかなり楽しかった。

反省点

以前にも様々な場面で感じてたけど、一つのことにじっくり取り組む訓練が十分でないことを痛感。
収集した情報を応用できなかったことと、知識が足りず他の方の解法を理解出来ないのが悔しい。

ソースコード

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <fstream>
#include <list>
#include <sys/time.h>

using namespace std;

class FixTheFence{
private:
    
    struct dfsinfo{
        int x;
        int y;
        list<int>visited;
        string route;
    };
    
    struct result{
        int row;
        int col;
        string route;
    };
    
    double score(const vector<string>& diagram,result res){
        int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
        string r="RDLU";
        
        int size = (int)diagram.size();
        int x=res.col,y=res.row;
        
        //セルごとのフェンスの数
        int fence[100][100];
        
        for (int i=0; i<100; i++) {
            for (int j=0; j<100; j++) {
                fence[i][j]=0;
            }
        }
        
        
        //ルート
        for (int i=0; i<res.route.size(); i++) {
            int angle=0;
            
            //進行方向の検出
            for (int j=0; j<4; j++) {
                if (res.route[i]==r[j]) {
                    angle=j;
                    break;
                }
            }
            
            //フェンス計上
            switch (angle) {
                case 0:
                    fence[y][x]++;
                    fence[y-1][x]++;
                    
                    break;
                
                case 1:
                    fence[y][x]++;
                    fence[y][x-1]++;
                    
                    break;
                
                case 2:
                    fence[y][x-1]++;
                    fence[y-1][x-1]++;
                    
                    break;
                
                case 3:
                    fence[y-1][x]++;
                    fence[y-1][x-1]++;
                    
                    break;
            }
            
            //次の場所の設定
            x+=dx[angle];
            y+=dy[angle];
            
        }
        
        //合致数の計上
        int all=0,ok=0;
        for (int i=0; i<size; i++) {
            for (int j=0; j<size; j++) {
                if (diagram[i][j]!='-'){
                    all++;
                    if (diagram[i][j]==('0'+fence[i][j])) {
                        ok++;
                    }
                }
            }
        }
        
        return (double)ok/all;
        
    }
    
    double sec() {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    };
    
        
public:
    
    string findLoop(vector <string> diagram){
        srand((unsigned int)time(NULL));
        
        
        const double TIME_LIMIT=3.5;//オフライン:3.5,オンライン:9.7
        double start_time=sec();
        
        int edge[2][101][101];//[横・縦][y][x]
        
        int size=(int)diagram.size();
        
        
        for (int i=0; i<2; i++) {
            for (int j=0; j<101; j++) {
                for (int k=0; k<101; k++) {
                    edge[i][j][k]=0;
                }
            }
        }
        
        
        //「0」原則
        for (int i=0; i<size; i++) {
            for (int j=0; j<size; j++) {
                if (diagram[i][j]=='0') {
                    edge[0][i][j]=-1;
                    edge[0][i+1][j]=-1;
                    edge[1][i][j]=-1;
                    edge[1][i][j+1]=-1;
                }
            }
        }
        
        
        
        //0を回避しつつ進む深さ優先探索。
        int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
        string r="RDLU";
        
        //解答の設定
        vector<result>res;
        result base;
        base.row=0;
        base.col=0;
        base.route="RDLU";
        res.push_back(base);
        
        int row=0,col=0;
        
        while ((sec()-start_time)<=TIME_LIMIT){
            
            //初期位置の乱択
            row=rand()%size;
            col=rand()%size;
            
            //スタックの設定
            stack<dfsinfo> st;
            
            dfsinfo first;
            first.x=col;
            first.y=row;
            first.route="";
            st.push(first);
            
            while (st.size()>0&&(sec()-start_time)<=TIME_LIMIT) {
                
                dfsinfo now;
                now=st.top();st.pop();
                
                //解の一つが見つかったら打ち切る
                if (now.route.size()>0&&now.x==col&&now.y==row) {
                    result re;
                    re.row=row;
                    re.col=col;
                    re.route=now.route;
                    res.push_back(re);
                    break;
                }
                
                //右上左下の順で調べる
                for (int i=0; i<4; i++) {

                    int nowx=now.x+dx[i],nowy=now.y+dy[i];
                    
                    //禁止チェック
                    
                    //範囲外
                    if (nowx<0||nowx>=size||nowy<0||nowy>=size) continue;
                    
                    //通過済
                    list<int>::iterator pos;
                    pos = find( now.visited.begin(), now.visited.end(), nowx+nowy*size);
                    
                    if (pos!=now.visited.end()) continue;
                    
                    //0除外
                    
                    if(i==2&&now.x-1<0)cerr<<"now.x-1<0"<<endl;
                    else if(i==3&&now.y-1<0)cerr<<"now.y-1<0"<<endl;
                    
                    if(i==0&&edge[0][now.y][now.x]==-1)continue;
                    else if(i==1&&edge[1][now.y][now.x]==-1)continue;
                    else if(i==2&&edge[0][now.y][now.x-1]==-1)continue;
                    else if(i==3&&edge[1][now.y-1][now.x]==-1)continue;
                    
                    
                    //全て通ってるからスタックに追加
                    dfsinfo next;
                    next.x=nowx;
                    next.y=nowy;
                    next.visited=now.visited;
                    next.visited.push_back(nowx+nowy*size);
                    next.route=now.route+r[i];
                    st.push(next);
                }
            }
        }
        
        
        cerr<<"search:ok"<<endl;
        for (int i=0; i<res.size(); i++) {
            cerr<<i<<" "<<res[i].row<<" "<<res[i].col<<" "<<res[i].route<<endl;
        }
        
        double max_score=0;
        int num=0;
        
        for (int i=0; i<res.size(); i++) {
            double s=score(diagram,res[i]);
            if (s>max_score) {
                max_score=s;
                num=i;
            }
        }
        
        
        cerr<<"output:ok"<<endl;
        
        stringstream ss;
        
        ss<<res[num].row<<" "<<res[num].col<<" "<<res[num].route;
        
        cerr<<"use:"<<ss.str()<<endl;
        fprintf(stderr,"Score = %.16lf\n",max_score);
        
        return ss.str();
    };
    
};

int main()
{
    int SZ;
    cin>>SZ;
    
    vector<string> diagram(SZ);
    
    for (int i=0; i < SZ; i++){
        cin>>diagram[i];
    }
    
    FixTheFence f;
    
    cout<<f.findLoop(diagram)<<endl;
    
    return 0;
}