首页 > 试题广场 >

蘑菇阵

[编程题]蘑菇阵
  • 热度指数:23314 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
现在有两个好友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位小数)
示例1

输入

2 2 1
2 1

输出

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

}

发表于 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)
#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)
//可行路径/总路径的方法不对,讨论里说道用概率求。
#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)
#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)
//运行通过
#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)
#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)
刚开始用路径数做,一直不对。纠结了好久,看了题解才想明白错在哪。
因为走不同路径的概率是不相等的。 
如   :
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)
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)
递归一下,就没了。

#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)
//要使用动态规划,注意每个点的概率来源,第一行的点,如(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)
//直接用概率进行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)
#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)