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

Community
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};
//４方向のそれぞれに対して進む確率
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) {
//既に訪れているならば０を返す
if(grid[x][y]) return(0);
//探索の深さが０になったら１を返す
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