読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

Project Euler 83 Path sum: four ways

問題を見た時からdijkstra法だと分かっていたが集中してやりたかったので敢えて取っておいた問題

#include <bits/stdc++.h>
using namespace std;
static const int WHITE = 1;
static const int GRAY  = 2;
static const int BLACK = 3;
static const int INF = 1<<21;
static const int MAX_N = 1000;
static const int N = 80;
int d[N][N];
int color[N][N];
int M[N][N];
int sx,sy,gx,gy;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

void dijkstra()
{
    int mincost;
    //初期化
    for(int y=0;y<N;y++){
        for(int x=0;x<N;x++){
            color[y][x]=WHITE;
            d[y][x]=INF;
        }
    }
    color[sy][sx]=GRAY;
    d[sy][sx]=M[sy][sx];

    while(true){
        //集合Sに隣接している頂点のうち最もコストの小さい頂点を探す
        mincost=INF;
        int uy=-1,ux=-1;
        for(int y=0;y<N;y++){
            for(int x=0;x<N;x++){
                if(color[y][x]!=BLACK && d[y][x]<mincost){
                    mincost=d[y][x];
                    uy=y;ux=x;
                }
            }
        }
        if(uy==-1 || ux==-1)break;//集合Sの更新が無かったら終了
        color[uy][ux]=BLACK;//その頂点を集合Sに挿れる
        //集合Sに隣接している頂点のd[v]を更新
        for(int i=0;i<4;i++){
            int vy=uy+dy[i],vx=ux+dx[i];
            if(0<=vy && vy<N && 0<=vx && vx<N){
                if(color[vy][vx]!=BLACK){
                    if(d[vy][vx]>d[uy][ux]+M[vy][vx]){
                        d[vy][vx]=d[uy][ux]+M[vy][vx];
                        color[vy][vx]=GRAY;
                    }
                }
            }
        }
    }
}

vector<string> split(const string &s, char delim)
{
    //文字列から文字をkeyにして分割する
    vector<string> elems;
    stringstream ss(s);
    string item;
    while(getline(ss,item,delim)){
        if(!item.empty()){
            elems.push_back(item);
        }
    }
    return elems;
}

int main()
{
    //test.txt からint型二次元配列をinput
    std::ifstream ifs("test.txt");
    std::string str;
    int i=0,j;
    while(getline(ifs,str))
    {
        std::cout<< str << std::endl;
        vector<string> s = split(str,',');
        for(int j=0;j<80;j++){
            M[i][j] = atoi(s[j].c_str());
        }
        i++;
    }
    cout<<"--------------------------"<<endl;
    sx=0,sy=0;
    gx=N-1,gy=N-1;
    dijkstra();
    cout<<d[gy][gx]<<endl;
    return 0;
}

C++でファイルの読み込み
複数行の,で区切られた数値を二次元配列に格納する処理

std::ifstream ifs("test.txt");
std::string str;
int i=0,j;
while(getline(ifs,str))
{
    std::cout<< str << std::endl;
    vector<string> s = split(str,',');
    for(int j=0;j<80;j++){
        M[i][j] = atoi(s[j].c_str());
        }
    i++;
}