Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What is going on with this article?
@tukejonny

壊れたロボット

More than 5 years have passed since last update.

 深さ優先探索を実践で実装出来ないなぁ・・・練習数が足りないのが原因だと言う事は分かっているので、ひたすら頑張るしか無いですね・・・
SRM425 Div2 Level2
我ながらおばかなコード書いてるなぁ・・・(笑)


public class Main {
    double[] dir;
    double[] allProbability;

    boolean ok(int before, int next) {
        if(before == 0 && next == 1 || before == 1 && next == 0)      return(false);
        else if(before == 2 && next == 3 || before == 3 && next == 2) return(false);
        return(true);
    }

    double dfs(int depth, double sum, int before) {
        double ret = 0;
        if(depth < 0) return(1);

        for(int r = 0; r < dir.length; r++) {
            if(!ok(before, r)) continue;
            sum *= dfs(depth - 1, sum * dir[r], r); 
            ret += sum;
        }

        return(ret);
    }

    double getProbability(int n, int east, int west, int south, int north) {
        dir = new double[]{(double)east / 100.0, (double)west / 100.0, (double)south / 100.0, (double)north / 100.0};
        if(n == 1) return(1);
        double ans = dfs(n, 1, 0);
        return(ans);
    }

    void doIt() {
        int n = 2;
        int east = 25;
        int west = 25;
        int south = 25;
        int north = 25;
        System.out.println(getProbability(n, east, west, south, north));
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new Main().doIt();
    }
}

答え

     //座標        
     boolean[][] grid = new boolean[100][100];
     //現在座標に、東は+(1, 0)、西は+(-1, 0)、南は+(0, -1)、北は+(0, -1)の処理をすれば、座標移動を実現出来る。
    int vx[] = {1, -1, 0, 0};
    int vy[] = {0, 0, 1, -1};
        //4方向のそれぞれに対して進む確率
    double[] prob = new double[4];

    public double getProbability(int n, int east, int west, int south, int north) {
                //確率を格納
        prob[0] = east / 100.0;
        prob[1] = west / 100.0;
        prob[2] = south / 100.0;
        prob[3] = north / 100.0;

        return(dfs(50, 50, n));
    }

    double dfs(int x, int y, int n) {
          //既に訪れているならば0を返す
        if(grid[x][y]) return(0);
                //探索の深さが0になったら1を返す
        if(n == 0) return(1);

          //現在座標をtrueにしておく
        grid[x][y] = true;
        double ret = 0;
        for(int r = 0; r < 4; r++) {
            //east, west, south, northの順にロボットを動かす
            ret += dfs(x + vx[r], y + vy[r], n - 1) * prob[r];
        }
                //現在座標に対して処理を終えたのでfalseを格納
        grid[x][y] = false;
        return(ret);
    }
3
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?