现在有两个好友A和B，住在一片长有蘑菇的由n＊m个方格组成的草地，A在(1,1),B在(n,m)。现在A想要拜访B，由于她只想去B的家，所以每次她只会走(i,j+1)或(i+1,j)这样的路线，在草地上有k个蘑菇种在格子里(多个蘑菇可能在同一方格),问：A如果每一步随机选择的话(若她在边界上，则只有一种选择)，那么她不碰到蘑菇走到B的家的概率是多少？
[编程题]蘑菇阵
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
int m = scan.nextInt();
int k = scan.nextInt();
int[][] map = new int[n+1][m+1];
while(k != 0){
int row = scan.nextInt();
int col = scan.nextInt();
map[row][col] = 1;
k--;
}
double[][] dp = new double[n+1][m+1];
dp[1][1] = 1.0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(!(i == 1 && j == 1)){
dp[i][j] = dp[i-1][j]*(j==m?1:0.5) + dp[i][j-1]*(i==n?1:0.5);
}
if(map[i][j] == 1){
dp[i][j] = 0;
}
}
}
System.out.printf("%.2f",dp[n][m]);
System.out.println();
}
}
}
发表于 2023-03-11 20:16:10
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
int[][] elem = new int[n+1][m+1];
for (int i = 0; i < k; i++) {
elem[scanner.nextInt() ][scanner.nextInt() ] = 1;
}
double[][] dp = new double[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) {
dp[1][1] = 1;
continue;
}
if (elem[i][j ] == 1) {//这个位置是蘑菇
dp[i][j] = 0;
} else
dp[i][j] = dp[i - 1][j] * (j == m ? 1 : 0.5) + dp[i][j - 1] * (i == n ? 1 : 0.5); //边界的时候，概率为1
}
}
System.out.printf("%.2f\n" ,dp[n][m]);
}
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
int[][] elem = new int[n+1][m+1];
for (int i = 0; i < k; i++) {
elem[scanner.nextInt() ][scanner.nextInt() ] = 1;
}
double[][] dp = new double[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) {
dp[1][1] = 1;
continue;
}
if (elem[i][j ] == 1) {//这个位置是蘑菇
dp[i][j] = 0;
} else
dp[i][j] = dp[i - 1][j] * (j == m ? 1 : 0.5) + dp[i][j - 1] * (i == n ? 1 : 0.5); //边界的时候，概率为1
}
}
System.out.printf("%.2f\n" ,dp[n][m]);
}
}
}
发表于 2022-09-20 23:48:41
回复(0)
//动态规划的思想
import java.util.*;
public class Main{
public static double dp(int[][] arr,int n,int m){
double[][] res = new double[n+1][m+1];
res[1][1] = 1.0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
//如果A不在（1,1）位置，此时他有两个方向可以走（向左或者向右），概率均为0.5
//在最后一列和最后一行的时候他只有一个方向可以走，所以概率为1.0 if(!(i == 1 && j == 1)){
res[i][j] = res[i - 1][j] * (j == m ? 1.0 : 0.5) + res[i][j - 1] * (i == n ? 1.0 : 0.5);
}
//如果arr[i][j]位置是蘑菇，则不可能走到该位置，所以该位置的概率为0.0
if(arr[i][j] == 1){
res[i][j] = 0.0;
}
}
}
return res[n][m];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n+1][m+1];
int k = sc.nextInt();
while(k != 0){
int x = sc.nextInt();
int y = sc.nextInt();
arr[x][y] = 1;
k--;
}
double result = dp(arr,n,m);
System.out.printf("%.2f\n",result);
}
}
}
编辑于 2022-05-29 21:32:56
回复(0)
// package baidu.P1;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt()){
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
int flag[][] = new int[n][m];
for (int i = 0; i < k; i++) {
int one = scanner.nextInt();
int two = scanner.nextInt();
flag[one-1][two-1] = 1;
}
double dp[][] = new double[n][m];
for (int i = m - 2; i >= 0; i--) {
if(flag[n-1][i] != 1){
dp[n-1][i] = 1;
}else{
int temp = i;
while(temp >= 0){
dp[n-1][temp] = 0;
temp--;
}
break;
}
}
for (int i = n - 2; i >= 0; i--) {
if(flag[i][m-1] != 1){
dp[i][m-1] = 1;
}else{
int temp = i;
while(temp >= 0){
dp[i][m-1] = 0;
temp--;
}
break;
}
}
for (int i = n - 2; i >= 0 ; i--) {
for (int j = m - 2; j >= 0 ; j--) {
if(flag[i][j] == 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i + 1][j] * 0.5 + dp[i][j + 1] * 0.5;
}
}
}
System.out.printf("%.2f", dp[0][0]);
System.out.println();
}
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt()){
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
int flag[][] = new int[n][m];
for (int i = 0; i < k; i++) {
int one = scanner.nextInt();
int two = scanner.nextInt();
flag[one-1][two-1] = 1;
}
double dp[][] = new double[n][m];
for (int i = m - 2; i >= 0; i--) {
if(flag[n-1][i] != 1){
dp[n-1][i] = 1;
}else{
int temp = i;
while(temp >= 0){
dp[n-1][temp] = 0;
temp--;
}
break;
}
}
for (int i = n - 2; i >= 0; i--) {
if(flag[i][m-1] != 1){
dp[i][m-1] = 1;
}else{
int temp = i;
while(temp >= 0){
dp[i][m-1] = 0;
temp--;
}
break;
}
}
for (int i = n - 2; i >= 0 ; i--) {
for (int j = m - 2; j >= 0 ; j--) {
if(flag[i][j] == 1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i + 1][j] * 0.5 + dp[i][j + 1] * 0.5;
}
}
}
System.out.printf("%.2f", dp[0][0]);
System.out.println();
}
}
}
发表于 2022-04-18 16:42:11
回复(0)
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Scanner;
/*题目描述
现在有两个好友A和B，住在一片长有蘑菇的由n＊m个方格组成的草地，
A在(1,1),B在(n,m)。现在A想要拜访B，由于她只想去B的家，所以每次她只会走(i,j+1)或(i+1,j)这样的路线，
在草地上有k个蘑菇种在格子里(多个蘑菇可能在同一方格),问：A如果每一步随机选择的话(若她在边界上，则只有一种选择)，
那么她不碰到蘑菇走到B的家的概率是多少？
输入描述:
第一行N，M，K(1 ≤ N,M ≤ 20, k ≤ 100),N,M为草地大小，接下来K行，每行两个整数x，y，代表(x,y)处有一个蘑菇。
输出描述:
输出一行，代表所求概率(保留到2位小数)*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String[] str1 = scanner.nextLine().split(" ");
int n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
int k = Integer.parseInt(str1[2]);
ArrayList<MoGu> arrayList = new ArrayList<>();
Main moGuZhen = new Main();
for (int i = 0; i < k; i++) {
String[] str2 = scanner.nextLine().split(" ");
int x = Integer.parseInt(str2[0]);
int y = Integer.parseInt(str2[1]);
MoGu moGu = moGuZhen.new MoGu(x, y);
arrayList.add(moGu);
}
int[][] zhen = new int[n][m];
for (int i = 0; i < arrayList.size(); i++) {
MoGu moGu = arrayList.get(i);
int x = moGu.getX();
int y = moGu.getY();
zhen[x - 1][y - 1] = -1;
}
moGuZhen.moGuZhen(zhen, n, m);
}
}
private class MoGu {
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public MoGu(int x, int y) {
this.x = x;
this.y = y;
}
private int x;
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
private int y;
}
public void moGuZhen(int[][] zhen, int n, int m) {
double[][] dp = new double[zhen.length][zhen[0].length];
dp[0][0] = 1;
for (int j = 1; j < m; j++) {
if (zhen[0][j] == -1) {
dp[0][j] = 0;
continue;
}
if (n == 1) {
dp[0][j] = dp[0][j - 1] * 1;
} else {
dp[0][j] = dp[0][j - 1] * 0.5;
}
}
for (int i = 1; i < n; i++) {
if (zhen[i][0] == -1) {
dp[i][0] = 0;
continue;
}
if (m == 1) {
dp[i][0] = dp[i - 1][0] * 1;
} else {
dp[i][0] = dp[i - 1][0] * 0.5;
}
}
for (int o = 1; o < n; o++) {
for (int p = 1; p < m; p++) {
if (zhen[o][p] == -1) {
dp[o][p] = 0;
continue;
}
if ((o == n - 1) && (p != m - 1)) {
dp[o][p] = dp[o][p - 1] * 1 + dp[o - 1][p] * 0.5;
continue;
}
if ((p == m - 1) && (o != n - 1)) {
dp[o][p] = dp[o - 1][p] * 1 + dp[o][p - 1] * 0.5;
continue;
}
if ((p == m - 1) && (o == n - 1)) {
dp[o][p] = dp[o - 1][p] + dp[o][p - 1];
continue;
}
dp[o][p] = dp[o - 1][p] * 0.5 + dp[o][p - 1] * 0.5;
}
}
/* for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}*/
double result = dp[n - 1][m - 1];
// System.out.println("result: " + result);
String res = new DecimalFormat("0.00").format(result);
System.out.println(res);
}
}
大佬们的三元判断学不来。
发表于 2018-06-10 18:44:42
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
int m = input.nextInt();
int n = input.nextInt();
int k = input.nextInt();
int [][] mg=new int[m][n];
for(int i=0; i<k; i++){
int x= input.nextInt()-1;
int y= input.nextInt()-1;
mg[x][y]=1;
}
possibility(mg);
}
input.close();
}
public static void possibility(int [][]mg){
int m=mg.length;
int n=mg[0].length;
//corner case:只有一行或者一列
if(m==1||n==1){
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mg[i][j]==1){
System.out.println("0.00");
return;
}
}
}
System.out.println("1.00");
return;
}
double [][]pos=new double[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0 && j==0)
pos[i][j]=1;
else if(mg[i][j]==1)
pos[i][j]=0;
else if(i==0)
pos[i][j]= 0.5*pos[i][j-1];
else if(j==0)
pos[i][j]= 0.5*pos[i-1][j];
else if(i==m-1&&j!=n-1)
pos[i][j]= pos[i][j-1]+0.5*pos[i-1][j];
else if(i!=m-1&&j==n-1)
pos[i][j]= 0.5*pos[i][j-1]+pos[i-1][j];
else if(i==m-1&&j==n-1)
pos[i][j]=pos[i][j-1]+ pos[i-1][j];
else
pos[i][j]= 0.5*(pos[i][j-1]) + 0.5*(pos[i-1][j]);
}
}
System.out.printf("%.2f\n",pos[m-1][n-1]);
}
}
发表于 2017-04-27 05:42:28
回复(0)
package NewCoder.XiaoZhaoZhenTi; import java.util.Scanner; public class test2_3 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int N = scanner.nextInt(); int M = scanner.nextInt(); int K = scanner.nextInt(); int[][] matrix = new int[N][M]; for (int i = 0; i < K; i++) { int x = scanner.nextInt(); int y = scanner.nextInt(); matrix[x - 1][y - 1] = 1;// 有蘑菇 } double[][] noBomb = new double[N][M];// 记录没有蘑菇到达当前地点的概率 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (i == 0 && j == 0) { noBomb[i][j] = 1; continue; } if (matrix[i][j] == 0) { noBomb[i][j] = getResult(i - 1, j, N, M, noBomb) * getGaiLv(i - 1, j, N, M) + getResult(i, j - 1, N, M, noBomb) * getGaiLv(i, j - 1, N, M); // 等于左边无蘑菇到达概率*左边到当前过来的概率+等于上边无蘑菇的概率*上边过来的概率 } else { noBomb[i][j] = 0;// 有蘑菇,此点直接为0 } } } System.out.println(String.format("%.2f", noBomb[N - 1][M - 1])); } } public static double getResult(int x, int y, int N, int M, double matrix[][]) { if (x >= 0 && x < N && y >= 0 && y < M) { return matrix[x][y]; } else { return 0; } } public static double getGaiLv(int x, int y, int N, int M) { if (x == N - 1 || y == M - 1) { return 1;// 边界过来是1 } else { return 0.5;// 其余则是0.5过来的可能性 } } }
发表于 2017-04-18 21:09:29
回复(0)
import java.util.*;
import java.math.*;
import java.text.NumberFormat;
import java.math.*;
import java.text.NumberFormat;
public class Main{
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
String a=scanner.nextLine();
String[] b=a.split(" ");
List<int[]> L=new ArrayList<int[]>();
int N=Integer.parseInt(b[0]);
int M=Integer.parseInt(b[1]);
int K=Integer.parseInt(b[2]);
for(int i=0;i<K;i++){
a=scanner.nextLine();
b=a.split(" ");
int[] u=new int[2];
u[0]=Integer.parseInt(b[0]);
u[1]=Integer.parseInt(b[1]);
L.add(u);
}
NumberFormat nf = NumberFormat.getNumberInstance();
nf.setMaximumFractionDigits(2);
double d=new Main().Gailv(N,M,L);
System.out.println(String.format("%.2f", d));
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
String a=scanner.nextLine();
String[] b=a.split(" ");
List<int[]> L=new ArrayList<int[]>();
int N=Integer.parseInt(b[0]);
int M=Integer.parseInt(b[1]);
int K=Integer.parseInt(b[2]);
for(int i=0;i<K;i++){
a=scanner.nextLine();
b=a.split(" ");
int[] u=new int[2];
u[0]=Integer.parseInt(b[0]);
u[1]=Integer.parseInt(b[1]);
L.add(u);
}
NumberFormat nf = NumberFormat.getNumberInstance();
nf.setMaximumFractionDigits(2);
double d=new Main().Gailv(N,M,L);
System.out.println(String.format("%.2f", d));
}
scanner.close();
}
public double Gailv(int N,int M,List<int[]> L){
if(N==1||M==1)return 1;
double[][] x=new double[N][M];
x[0][0]=1;
boolean b=true;
for(int i=1;i<N;i++){
if(b){
if(judge(i,0,L)){
x[i][0]=Math.pow(0.5,i);
}
else {b=false;x[i][0]=0;}
}
else x[i][0]=0;
}
b=true;
for(int i=1;i<M;i++){
if(b){
if(judge(0,i,L)){
x[0][i]=Math.pow(0.5,i);
}
else {b=false;x[0][i]=0;}
}
else x[0][i]=0;
}
for(int i=1;i<N;i++){
for(int j=1;j<M;j++){
if(judge(i,j,L)){
double q=x[i][j-1]/2,p=x[i-1][j]/2;
if(i==N-1)q*=2;
if(j==M-1)p*=2;
x[i][j]=q+p;
}
else x[i][j]=0;
}
}
return x[N-1][M-1];
}
public boolean judge(int a,int b,List<int[]> L){
a+=1;b+=1;
for(int i=0;i<L.size();i++){
if(L.get(i)[0]==a&&L.get(i)[1]==b)
return false;
else continue;
}
return true;
}
}
scanner.close();
}
public double Gailv(int N,int M,List<int[]> L){
if(N==1||M==1)return 1;
double[][] x=new double[N][M];
x[0][0]=1;
boolean b=true;
for(int i=1;i<N;i++){
if(b){
if(judge(i,0,L)){
x[i][0]=Math.pow(0.5,i);
}
else {b=false;x[i][0]=0;}
}
else x[i][0]=0;
}
b=true;
for(int i=1;i<M;i++){
if(b){
if(judge(0,i,L)){
x[0][i]=Math.pow(0.5,i);
}
else {b=false;x[0][i]=0;}
}
else x[0][i]=0;
}
for(int i=1;i<N;i++){
for(int j=1;j<M;j++){
if(judge(i,j,L)){
double q=x[i][j-1]/2,p=x[i-1][j]/2;
if(i==N-1)q*=2;
if(j==M-1)p*=2;
x[i][j]=q+p;
}
else x[i][j]=0;
}
}
return x[N-1][M-1];
}
public boolean judge(int a,int b,List<int[]> L){
a+=1;b+=1;
for(int i=0;i<L.size();i++){
if(L.get(i)[0]==a&&L.get(i)[1]==b)
return false;
else continue;
}
return true;
}
}
发表于 2017-04-10 20:29:18
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
double[][] dp = new double[n + 1][m + 1];
for (int i = 0; i < k; i ++ ) {
dp[sc.nextInt()][sc.nextInt()] = 1;
}
dp[1][1] = 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if(i == 1 && j == 1) continue;
if(dp[i][j] == 1)
dp[i][j] = 0;
else {
if(j == m && i != n)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] * 0.5;
else if(j != m && i == n)
dp[i][j] = dp[i - 1][j] * 0.5 + dp[i][j - 1];
else if(j == m && i == n)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
else
dp[i][j] = dp[i - 1][j] * 0.5 + dp[i][j - 1] * 0.5;
}
}
}
System.out.println(String.format("%.2f", dp[n][m]));
}
}
}
发表于 2016-08-30 21:14:09
回复(0)
import java.util.*; public class Main { public static void main(String[] args){ Scanner input = new Scanner(System.in); while(input.hasNext()){ int N = input.nextInt(); int M = input.nextInt(); int K = input.nextInt(); double[][] poss = new double[N][M]; boolean[][] mogu = new boolean[N][M]; poss[0][0] = 1; for(int i = 0; i < K; i++){ int a = input.nextInt(); int b = input.nextInt(); mogu[a-1][b-1] = true; } for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ if(mogu[i][j]){ poss[i][j] = 0; }else if(i != 0 && j != 0)){ poss[i][j] = (j==0?0:(i==N-1?1:0.5)*poss[i][j-1])+(i==0?0:(j==M-1?1:0.5)*poss[i-1][j]); } } } System.out.println(String.format("%.2f",poss[N-1][M-1])); } } }
使用三目判断语句会更简洁
编辑于 2016-08-25 23:33:30
回复(0)
package mushroom;
import java.util.Scanner;
public class Main {
public static double dealPre(int x,int y,int N,int
M,double[][] arr){
/**该函数主要确定有几个后继节点（1或者2）
* 然后返回他们的概率
*
*/
//(x,y) 表示 该前驱节点
if(y==M-1){ //该前驱只有下后继，没有右后继
return arr[x][y];
}
else if(x==N-1){ // 该前驱只有右后继，没有下后继
return arr[x][y];
}
else{// 有2个后继
return arr[x][y]*0.5;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N =0;
int M =0;
int K =0;
while(sc.hasNext()){
N = sc.nextInt();
M = sc.nextInt();
K = sc.nextInt();
double[][] arr = new double[N][M];
boolean[][] map = new boolean[N][M];
int temp0;
int temp1;
for(int i=0;i<K;i++){
temp0 =sc.nextInt();
temp1 =sc.nextInt();
map[temp0-1][temp1-1]=true;
}
for(int i=0; i<N;i++){
for(int j=0;j<M;j++){
if(i==0&&j==0){
arr[i][j]=1;
//起点概率为1
}
// 任何一点的概率都是由上和左 2部分构成
else if(map[i][j]==true){
arr[i][j]=0;
// 有蘑菇点 概率为0
}
else if(j==0){ // 有上前驱，没有左前驱
//第一竖列
arr[i][j] = dealPre(i-1,j,N,M,arr);
}
else if(i==0){
// 只有左前驱，没有上前驱，只继承左前驱概率的拓扑
arr[i][j] = dealPre(i,j-1,N,M,arr);
}
else{
// 既有左前驱，又有上前驱，把2个加在一起
arr[i][j] =
dealPre(i-1,j,N,M,arr)+dealPre(i,j-1,N,M,arr);
}
}
}
System.out.println(String.format("%.2f",
(arr[N-1][M-1])));
}
}
}
发表于 2016-06-15 10:04:15
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-13 11:01:33
-
2023-03-11 20:15:51 -
2023-02-03 19:31:07
-
2023-01-04 16:03:11 -
2022-12-28 14:23:46
相关试题
-
评论(178) 来自百度2016研发工程师在...
-
评论(257) 来自百度2016研发工程师在...
-
评论(148) 来自百度2016研发工程师在...
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
