[백준 1405] 미친 로봇(JAVA/C++)

 

https://www.acmicpc.net/problem/1405

 

1405번: 미친 로봇

 

 

 

[JAVA]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{

	static int N;
	static double ans=0.0;
	static double[] percent;
	static boolean[][] visit= new boolean[30][30];
	static int[] dx= {0,0,1,-1};
	static int[] dy= {1,-1,0,0};
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		percent=new double[4];
		StringTokenizer st=new StringTokenizer(br.readLine()," ");
		N=Integer.parseInt(st.nextToken());
		
		for(int i=0; i<4; i++) {
			percent[i]=Integer.parseInt(st.nextToken())*0.01;
		}
		visit[14][14]=true;
		solve(14,14,0,1.0);
		System.out.println(ans);
	}
	private static void solve(int x, int y, int cnt, double chance) {
		if(cnt==N) {
			ans+=chance;
			return;
		}
		
		for(int i=0; i<4; i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(visit[nx][ny])continue;
			visit[nx][ny]=true;
			solve(nx,ny,cnt+1,chance*percent[i]);
			visit[nx][ny]=false;
		}
	}

}

 

 

[C++]

#include <iostream>
#include <iomanip>

using namespace std;

int N;
double ans;
double percent[4];
int map[30][30];
bool visited[30][30];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

void Dfs(int x, int y, double chance){
	if (N == 0){
		ans += chance;
		return;
	}
	visited[x][y] = true;
	for (int i = 0; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (!visited[nx][ny]){
			N--;
			Dfs(nx, ny, chance*percent[i]);
			N++;
			visited[nx][ny] = false;
		}
	}
}
int main(){
	cin >> N;
	int num;
	for (int i = 0; i < 4; i++){
		cin >> num;
		percent[i] = num * 0.01;
	}
	Dfs(15, 15, 1.0);
	cout << fixed;
	cout << setprecision(10) << ans << "\n";

	return 0;
}