蘑菇阵__牛客网

Java

忧郁的小菜鸟

import java.util.*;
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));

        }
        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)

潇潇古月

这个题目并不困难，只需要生成一个n*m的地图，首先将有蘑菇的该点设置为-1，表示不能碰到蘑菇，那么从<1, 1>出发，可达<1, 1>的概率就是map[1][1] = 1,对于一般情况，map[i][j] = (map[i][j-1] + map[i-1][j]) / 2，其中，如果map[i][j]、 map[i][j-1]、 map[i-1][j]如果分别为-1，则不计算对应部分，不过，对于i==n和j==m的情况下有所不同，因为此时只有一种移动方式，所以应该在多加上map[i][j-1]/2和map[i-1][j]/2，由此，map[n][m]就是达到终点的概率，代码如下：

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();
            int[][] xy = new int[k][2];
            for (int i = 0; i < k; i++) {
                xy[i][0] = sc.nextInt();
                xy[i][1] = sc.nextInt();
            }
            System.out.printf("%.2f", solve(n, m, xy));
        }
    }

    private static double solve(int n, int m, int[][] xy) {
        double[][] map = new double[n + 1][m + 1];
        for (int[] a : xy) {
            map[a[0]][a[1]] = -1;
        }
        map[1][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j] != -1) {
                    if (map[i - 1][j] != -1)
                        map[i][j] += j == m ? map[i - 1][j] : map[i - 1][j] / 2;
                    if (map[i][j - 1] != -1)
                        map[i][j] += i == n ? map[i][j - 1] : map[i][j - 1] / 2;
                }

            }
        }
        return map[n][m];
    }
}

编辑于 2017-08-10 14:47:57 回复(0)

Java

来学习的小张

//动态规划的思想
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)

Java

zzy远

// 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();
}
}

}

发表于 2022-04-18 16:42:11 回复(0)

Java

已注销

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)

C/C++

nbgao

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{     int N,M,K,x,y;     double dp[25][25];     bool has[25][25];          while(cin>>N>>M>>K)     {         memset(dp,0,sizeof(dp));         memset(has,false,sizeof(has));         for(int i=0;i<K;i++)         {             cin>>x>>y;             has[x][y] = true;         }         for(int i=1;i<=N;i++)             for(int j=1;j<=M;j++)             {                 if(i==1 && j==1)                 {                     dp[i][j] = 1;                     continue;                 }                 if(has[i][j])                 {                     dp[i][j] = 0;                     continue;                 }                 if(i==N && j==M)                 {                     dp[i][j] = dp[i-1][j] + dp[i][j-1];                     continue;                 }                 if(i==N)                 {                     dp[i][j] = dp[i-1][j]*0.5 + dp[i][j-1];                     continue;                 }                 if(j==M)                 {                     dp[i][j] = dp[i-1][j] + dp[i][j-1]*0.5;                     continue;                 }                 if(i==1)                 {                     dp[i][j] = dp[i][j-1]*0.5;                     continue;                 }                 if(j==1)                 {                     dp[i][j] = dp[i-1][j]*0.5;                     continue;                 }                 dp[i][j] = dp[i-1][j]*0.5 + dp[i][j-1]*0.5;             }         printf("%.2f\n", dp[N][M]);     }
     return 0;
}

发表于 2017-12-06 08:49:50 回复(0)

drdr

//可行路径/总路径的方法不对，讨论里说道用概率求。
#include<iostream>
#include<vector>

using namespace std;

int main(){
    int N, M, K;
    while(cin>>N>>M>>K){
        vector<vector<float>> input(N+1, vector<float>(M+1, 0));
        int x, y;
        for(int i = 0; i < K; ++i){
            cin>>x>>y;
            input[x][y] = -1;      //-1表示有蘑菇
        }
        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= M; ++j){
                if(i==1 && j == 1) input[1][1] = 1;
                else if(input[i][j] != -1){
                    if(i != N && j != M)
                    	input[i][j] = input[i-1][j]*0.5 + input[i][j-1]*0.5;
                    if(i == N && j != M) 
                        input[i][j] = input[i-1][j]*0.5 + input[i][j-1];
                    if(i != N && j == M)
                        input[i][j] = input[i-1][j] + input[i][j-1]*0.5;
                    if(i == N && j == M) 
                        input[i][j] = input[i-1][j] + input[i][j-1];
                }
                else input[i][j] = 0;
          	}
        }
		printf("%.2f\n", input[N][M]);
    }
    return 0;
}

发表于 2017-07-12 16:36:52 回复(1)

阿里淘系技术部-营销工具

#include <iostream>
#include <cstring>
using namespace std;
int map[26][26];
double dp[26][26];
int N, M, K;
void init()
{
    memset(map, 0, sizeof(map));
    for(int i = 0; i <= N; i++)
        for(int j = 0; j <= M; j++)
            dp[i][j] = 0;
}
int judge(int x, int y)
{
    return x <= N && x >= 1 && y <= M && y >= 1;
}
int main()
{
    while(scanf("%d%d%d", &N, &M, &K) != EOF)
    {
        init();
        for(int i = 0; i < K; i++)
        {
            int x;
            int y;
            scanf("%d%d", &x, &y);
            map[x][y] = 1;
        }
        dp[1][1] = 1;
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= M; j++)
            {
                if(map[i][j] == 1)
                    dp[i][j] = 0;
                if(judge(i + 1, j) && judge(i, j + 1))
                {
                    dp[i + 1][j] += dp[i][j] * 0.5;
                    dp[i][j + 1] += dp[i][j] * 0.5;
                }
                else if(judge(i + 1, j))
                    dp[i + 1][j] += dp[i][j];
                else if(judge(i, j + 1))
                    dp[i][j + 1] += dp[i][j];

            }
        }
        printf("%.2lf\n", dp[N][M]);
    }
    return 0;
}
/*
 1 0.5 0.25
 0.5 0 0.25
 0 0 0.25

 1 0.5
 0.5 1
*/

编辑于 2017-03-28 23:04:02 回复(0)

牛客909508号

#include<iostream>
#include<iomanip>

using namespace std;

int main()
{
   int N,M,K,i,j,x,y;
   while(cin>>N>>M>>K)
   {
       float **p=new float *[N];
       for(i=0;i<N;i++)
       p[i]=new float[M];

       for(i=0;i<N;i++)
          for(j=0;j<M;j++)
            p[i][j]=1.0;

       for(i=0;i<K;i++)
       {
           cin>>x>>y;
           p[x-1][y-1]=0;
       }
       /*根据某步和上一步判断某步不遇到蘑菇的概率*/
       for(i=1;i<N;i++)     //左侧
          {
           if(p[i][0]==0||p[i-1][0]==0) //前面有蘑菇或本身有蘑菇
               p[i][0]=0;
            else if(M>1) p[i][0]=0.5*p[i-1][0]; //可下可右
          }
        for(j=1;j<M;j++)     //上侧
          {
           if(p[0][j]==0||p[0][j-1]==0) //前面有蘑菇或本身有蘑菇
               p[0][j]=0;
            else if(N>1) p[0][j]=0.5*p[0][j-1]; //可下可右
          }
        for(i=1;i<N;i++)     //其它
          for(j=1;j<M;j++)
          {
           if(p[i][j]==0) //本身有蘑菇
           continue;
            else
           p[i][j]=(i==N-1?1:0.5)*p[i][j-1]+(j==M-1?1:0.5)*p[i-1][j];
          }
        cout <<setiosflags(ios::fixed);
        cout <<setprecision(2) <<p[N-1][M-1]<<endl;

        for(i=0;i<N;i++)
        delete []p[i];
        delete []p;
   }
   return 0;

发表于 2015-10-17 10:23:39 回复(0)

cocxx

//运行通过
#include<iostream>
#include<iomanip>
using namespace std;

int main()
{
	int row, column, block;
	while (cin >> row >> column >> block)
	{
		if (block == 0)
			cout << setiosflags(ios::fixed) << setprecision(2) << 1.00 << endl;
		else{
			int * xptr = new int[block];
			int * yptr = new int[block];
			for (int i = 0; i < block; ++i)
				cin >> xptr[i] >> yptr[i];

			double ** iArray = new double*[row + 1];
			for (int i = 0; i <= row; ++i)
				iArray[i] = new double[column + 1];

			for (int i = 0; i <= row; ++i)
				iArray[i][0] = 0.0;
			for (int j = 0; j <= column; ++j)
				iArray[0][j] = 0.0;
			iArray[1][0] = 2.0;

			for (int i = 1; i <= row; ++i)
			for (int j = 1; j <= column; ++j)
				iArray[i][j] = 1.0;

			for (int i = 0; i < block; ++i)
				iArray[xptr[i]][yptr[i]] = 0.0;
			for (int i = 1; i <= row; ++i)
			for (int j = 1; j <= column; ++j)
			if (iArray[i][j] == 0.0)
				continue;
			else
				iArray[i][j] = (i == row ? iArray[i][j - 1] : 0.5*iArray[i][j - 1])
				+ (j == column ? iArray[i - 1][j] : 0.5*iArray[i - 1][j]);

			cout << setiosflags(ios::fixed) << setprecision(2) << iArray[row][column] << endl;

			for (int i = 0; i <= row; ++i)
				delete[]iArray[i];
			delete[]iArray;
			delete[]xptr;
			delete[]yptr;
		}
	}
	return 0;
}

发表于 2015-10-06 08:54:45 回复(0)

北在北方F


	#include <stdlib.h>



	#include <stdio.h>



	#include <math.h>



	//不能用可走路径数/总路径数进行计算



	//在下边界时，只能向右走，不能向下走，向右概率为1，右边界同理



	//而在非边界时，向下和向右的概率分别为0.5



	//我也是在看了Bestmouse皓的java代码意识到的， ths



	 



	



	



	int main(){



	    int n, m;



	    int cn, cm, k;



	    double **b;



	    int i,j;



	    while(~scanf("%d %d %d", &n, &m, &k)){



	        b=new double*[n]();



	        for(i=0; i<n; i++){



	            b[i]=new double[m]();



	            for(j=0; j<m; j++)



	                b[i][j]=1.0;



	        }



	        for(i=0; i<k; i++){



	            scanf("%d %d", &cn, &cm);



	            b[cn-1][cm-1]=0.0;



	        }



	        for(i=1; i<n; i++){



	            if(b[i][0]==0||b[i-1][0]==0)b[i][0]=0;



	            else if(m>1) b[i][0]=0.5*b[i-1][0];



	        }



	        for(j=1; j<m; j++){



	            if(b[0][j]==0||b[0][j-1]==0)b[0][j]=0;



	            else if(n>1) b[0][j]=0.5*b[0][j-1];



	        }



	        for(i=1; i<n; i++){



	            for(j=1; j<m; j++){



	                if(b[i][j]==0.0) continue;



	                else b[i][j]=(j==m-1?1:0.5)*b[i-1][j]+(i==n-1?1:0.5)*b[i][j-1];



	            }



	        }



	        printf("%0.2f\n", b[n-1][m-1]);



	        for(i=0; i<n; i++){



	            delete [] b[i];



	        }



	        delete [] b;



	    }



	}

编辑于 2015-09-28 16:44:14 回复(0)

饥饿的王者在刷题

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
//到最后一行，向右走的概率为1。同理在最后一列时候，向下走概率也为1。
//其它的都是用 fn[i][j] = 0.5*fn[i][j-1] + 0.5*fn[i-1][j];

int main()
{
	int n,m,k;
	while (cin>>n>>m>>k)
	{

		vector<vector<int>> mp(n+1, vector<int>(m+1, 0));
		vector<vector<float>> fn(n+1, vector<float>(m+1, 0));
		for (int i = 0; i < k; i++)
		{
			int x,y;
			cin>>x>>y;
			mp[x][y] = 1;
		}
		
		fn[1][1] = 1.0;

		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				if(i==1 && j==1)
					continue;
				if(mp[i][j]==1)
					fn[i][j] = 0.0;
				else
					fn[i][j] = (i==n?1:0.5)*fn[i][j-1] + (j==m?1:0.5)*fn[i-1][j];
			}
		}
		float ans = fn[n][m];
		cout.setf(ios::fixed);
		cout<<setprecision(2)<<ans<<endl;
	}

	return 0;
}

发表于 2016-06-08 11:40:31 回复(4)

QloKK

刚开始用路径数做，一直不对。纠结了好久，看了题解才想明白错在哪。

因为走不同路径的概率是不相等的。

如：

1 2 3

4 5 6

1->2 概率是0.5，2->3概率是0.5，3->6概率是1

1->2 概率是0.5，2->5概率是0.5，5->6概率是1

1->4 概率是0.5，4->5概率是 1，3->6概率是1

可以发现1-2-3-6与1-2-5-6的概率为0.25，而1-4-5-6概率为0.5

所以直接用可达路径数/总路径数求概率是不对的。

发表于 2015-10-02 15:46:39 回复(25)

Jason09

b矩阵存放蘑菇（a是b的一行），q矩阵存放转移概率（p是q的一行）；

参照着b矩阵对q矩阵进行动态规划；

就是边界太烦了；

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main()
{
	int n, m, k, i, j, x, y;
	vector<int> a;
    vector<float> p;
	vector<vector<int>> b;
    vector<vector<float>> q;
	while (cin >> n >> m >> k) {
		for (i = 0; i < n; ++i) {
			for (j = 0; j < m; ++j) { a.push_back(0); p.push_back(0.0); }
			b.push_back(a); q.push_back(p); a.clear(); p.clear();
		}
		for (i = 0; i < k; i++) { cin >> x >> y; b[x - 1][y - 1] = 1; }
		//--以上都是准备工作-----------------------------------------------------
		if (n == 1 || m == 1) { float ans = k == 0 ? 1 : 0; cout << fixed << setprecision(2) << ans << endl; }
		else {
			for (i = 0; i < n; ++i) {
				for (j = 0; j < m; ++j) {
					if (i == 0 && j == 0) { q[0][0] = 1.0; }
					else if (i == 0) { q[i][j] = b[i][j] == 0 ? q[i][j - 1] * 0.5 : 0; }
					else if (j == 0) { q[i][j] = b[i][j] == 0 ? q[i - 1][j] * 0.5 : 0; }
					else if (i == n - 1 && j > 0 && j < m - 1) { q[i][j] = b[i][j] == 0 ? q[i][j - 1] * 1 + q[i - 1][j] * 0.5 : 0; }
					else if (j == m - 1 && i > 0 && i < n - 1) { q[i][j] = b[i][j] == 0 ? q[i][j - 1] * 0.5 + q[i - 1][j] * 1 : 0; }
					else if (i == n - 1 && j == m - 1) { q[i][j] = b[i][j] == 0 ? q[i][j - 1] * 1 + q[i - 1][j] * 1 : 0; }
					else { q[i][j] = b[i][j] == 0 ? q[i][j - 1] * 0.5 + q[i - 1][j] * 0.5 : 0; }
				}
			}
			cout << fixed << setprecision(2) << q[i - 1][j - 1] << endl;
			b.clear();
			q.clear();
		}
	}
	return 0;
}

编辑于 2016-09-29 12:54:39 回复(0)

Jasooon

递归一下，就没了。

	#include <iostream>



	#include <cstdio>



	#include <cstring>



	#include <algorithm>



	#include <map>



	using namespace std;



	bool maze[23][23];



	double p[23][23];



	int main(){



	    int n,m,k;



	    while(~scanf("%d%d%d",&n,&m,&k)){



	        int x,y;



	        memset(maze,false,sizeof maze);



	        for(int i = 0;i<k;i++){



	            scanf("%d%d",&x,&y);



	            maze[x][y] = true;



	        }



	        memset(p,0,sizeof p);



	        p[1][1] = 1;



	        for(int i = 1;i<=n;i++)



	            for(int j = 1;j<=m;j++){



	                if( maze[i][j])



	                    continue;



	                double tmp = ((i == n || j == m ) ? 1 : 0.5 ) * p[i][j];



	                p[i+1][j] += tmp;



	                p[i][j+1] += tmp;



	            }



	        printf("%.2lf\n",p[n][m]);



	    }



	}

发表于 2016-08-26 20:35:08 回复(0)

肥宅

无障碍的情形，从（1,1）走到(n,m)需要m-1+n-1步，也就是从m-1+n-1步中选取m-1次拐弯，即所有情况有C(m-1+n-1, n-1)种；
有障碍的情形，DP转移方程： F(n,m)=noWay(n-1,m)?0:F(n-1,m)+noWay(n,m-1)?F(n,m-1)，O(m+n)时间可得到可行的走法数量F(n.m)
概率即为：F(n,m)/C(m-1+n-1, n-1)

,

编辑于 2015-09-27 07:26:01 回复(5)

莫笑☁️輕狂

感觉就是个排列组合的问题吧。。。

发表于 2015-09-24 19:03:09 回复(1)

qibofang

//要使用动态规划，注意每个点的概率来源，第一行的点，如(1,3)的概率来源只有它左边点(1,2)的1/2，
//第n行的点如(n,3)，概率来源为(n,2)+(n-1,3)*1/2，因为(n,2)只能往右走，概率为1。其他的特征点在程序段中列出
#include <iostream>
#include <iomanip>
#include<cstring>
using namespace std;
int has[25][25];//有无蘑菇
double dp[25][25];//能够到达每个格子的概率
 
int main(){
    int n, m, k;
    while(cin >> n >> m >> k){
        int i, j;
        memset(has, 0, sizeof(has));
        memset(dp, 0, sizeof(dp));
        int x, y;
        for(i = 0; i < k; ++i){
            cin >> x >> y;
            has[x][y] = 1;
        }
        for(i = 1; i <= n; ++i){
            for(j = 1; j <= m; ++j){
                if(i == 1 && j == 1) {dp[1][1] = 1; continue;}
                if(has[i][j]) {dp[i][j] = 0; continue;}
                if(i == n && j == m) {dp[i][j] = dp[i-1][j] + dp[i][j-1]; continue;}
                if(i == n) {dp[i][j] = dp[i-1][j]*0.5 + dp[i][j-1]; continue;}
                if(j == m) {dp[i][j] = dp[i-1][j] + dp[i][j-1]*0.5; continue;}
                if(i == 1) {dp[i][j] = dp[i][j-1]*0.5; continue;}
                if(j == 1) {dp[i][j] = dp[i-1][j]*0.5; continue;}
                dp[i][j] = dp[i][j-1]*0.5 + dp[i-1][j]*0.5;
            }
        }
        cout << fixed << setprecision(2) << dp[n][m] << endl;
    }
    return 0;
}

发表于 2016-08-23 12:54:28 回复(4)

Bestmouse皓

//直接用概率进行DP，用路径数是不对的
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        Scanner sca = new Scanner(System.in);
        while(sca.hasNext()){
        int n = sca.nextInt();
        int m = sca.nextInt();
        int k = sca.nextInt();
        boolean[][] map = new boolean[n][m];
        for(int i = 0; i < k; i++) {
            int x = sca.nextInt()-1;
            int y = sca.nextInt()-1;
            map[x][y] = true;
        }
        double[][] cw = new double[n][m];
        cw[0][0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(map[i][j]) cw[i][j] = 0;
                else if(i == 0 && j == 0) {}
                else cw[i][j] = (j-1<0?0:(i+1<n?cw[i][j-1]*0.5:cw[i][j-1]))+(i-1<0?0:(j+1<m?cw[i-1][j]*0.5:cw[i-1][j]));
                //System.out.print(String.format("%.5f",cw[i][j])+" ");
            }
            //System.out.println();
        }
        double res = cw[n-1][m-1];
        System.out.println(String.format("%.2f", res));
        }
    }
}

发表于 2015-09-28 00:46:45 回复(7)

莫慢待made

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
	int n, m, k;
	while(scanf("%d%d%d", &n, &m, &k) != EOF){
		vector<vector<int>> table((n+1), vector<int>(m+1));
		vector<vector<double>> P((n+1), vector<double>(m+1));
		int x, y;
		for(int i = 0; i < k; i++){
			scanf("%d%d", &x, &y);
			table[x][y] = 1;
		}
		P[1][1] = 1.0;      //起点概率为1
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(!(i == 1 && j ==1)){      //跳过起点
					P[i][j] = P[i-1][j]*(j == m? 1 : 0.5) + P[i][j-1]*(i == n?1:0.5);   //边界的时候，概率为1
					if(table[i][j] == 1) P[i][j] = 0;        //如果该点有蘑菇，概率置为0
				}
			}
		}
		printf("%.2lf\n", P[n][m]);
	}
}

思路：注意边界就行

发表于 2016-08-24 09:45:28 回复(4)

蘑菇阵

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题