幅優先探索

幅優先探索の問題をいくつか解いてみました。

幅優先探索はなかなか複雑になるので苦労しました。（もっと練習して慣れたい。）
実装力の無さを思い知らされました。

AOJ Volume1 0179 Mysterious Worm

Mysterious Worm | Aizu Online Judge

無駄が多いのかも。

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <utility>
using namespace std;
const int INF = 100000000;
const int dx[4]={0,1,0,-1};
const int dy[4]={-1,0,1,0};

int main() {
    while(1) {
        char str[15];
        scanf("%s",str);
        if(str[0]=='0')break;
        string body(str);
        set<string> s;
        queue< pair<string,int> > q;
        q.push(make_pair(body,0));
        s.insert(body);

        while(1) {
            if(q.size()==0) {printf("NA\n");break;}
            string str_tmp(q.front().first);
            int deep = q.front().second;
            q.pop();

            bool change=false;
            for(int i=0,str_size=str_tmp.size()-1;i<str_size;i++) {
                char c1=str_tmp[i], c2=str_tmp[i+1];
                if(c1!=c2) {
                    change=true;
                    string str_n(str_tmp);
                    if(c1!='r' && c2!='r') {
                        str_n[i]='r';
                        str_n[i+1]='r';
                    }
                    if(c1!='g' && c2!='g') {
                        str_n[i]='g';
                        str_n[i+1]='g';
                    }
                    if(c1!='b' && c2!='b') {
                        str_n[i]='b';
                        str_n[i+1]='b';
                    }

                    if(s.find(str_n)!=s.end()) continue;

                    s.insert(str_n);
                    q.push(make_pair(str_n, deep+1));
                }
            }
            if(!change) {
                printf("%d\n",deep);
                break;
            }
        }
    }
    return 0;
}

AOJ Volume5 0558 Cheese

Cheese | Aizu Online Judge

このJOI予選の問題は結構苦労しました。
アルゴリズムが思いついて実装してみるとRuntimeErrorになってしまいました。
実装力不足ですね (；・∀・)

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <utility>
#include <string.h>
using namespace std;
const int INF = 100000000;
const int dx[4]={0,1,0,-1};
const int dy[4]={-1,0,1,0};
class Pos{public:int x;int y;Pos(int X=0,int Y=0){x=X;y=Y;}Pos(const Pos &p){x=p.x;y=p.y;}};

struct P {
    int x,y,cost;
    P(int _x,int _y,int _cost) {
        x=_x;y=_y;cost=_cost;
    }
};

int H,W,N;
char twn[1002][1002];
bool check[1002][1002];

P getdist(int x, int y, char to) {
    queue<P> open;
    memset(check, 0, sizeof(check));
    open.push(P(x,y,0));
    while(!open.empty()) {
        P p=open.front(); open.pop();
        if(check[p.y][p.x]) continue;
        check[p.y][p.x] = true;

        if(twn[p.y][p.x]==to) return p;

        for(int i=0;i<4;i++) {
            int nx=p.x + dx[i];
            int ny=p.y + dy[i];
            if(nx>=0 && ny>=0 && nx<W && ny<H && twn[ny][nx]!='X') {
                P pn(nx,ny,p.cost+1);
                open.push(pn);
            }
        }
    }
}

int main() {
    int x, y;
    scanf("%d %d %d",&H,&W,&N);
    for(int i=0;i<H;i++) {
        scanf("%s", twn[i]);
        for(int j=0;j<W;j++) {
            if(twn[i][j]=='S') {
                x=j; y=i;
            }
        }
    }

    int ans=0;
    for(int mv=1;mv<=N;mv++) {
        P p=getdist(x,y, '0'+mv);
        ans+=p.cost;
        x=p.x; y=p.y;
    }
    printf("%d\n",ans);
    return 0;
}