http://acm.zznu.edu.cn/problem.php?id=1358

迷宫问题

时间限制: 1 Sec  内存限制: 128 MB

提交: 111  解决: 68

[][]

题目描述

ACM是一个喜欢玩游戏的小孩，他喜欢玩智力游戏，比如最近在玩走迷宫，这是一款超级耗费脑细胞的游戏。

和普通的走迷宫一样，游戏是一张迷宫图，其中有一些标记，'W'是墙，'.'是可走的路，起点在左上角，目标点在右下角。ACM从左上角出发，只能向下和向右走，游戏要你找出有多少种不同的走法。很有压力吧？那是对于非计算机专业的人来说！你怎么看？试试吧。

输入

首先输入一个整数T，表示接下来有T（0<T<=10）个测试实例。

每组测试实例第一行是两个整数n（0<n<=10）和m（0<m<=10），表示游戏是在一张n*m的迷宫图上进行，接下来是一个n*m的迷宫图。

具体输入见样例。

输出

每组样例输出一个整数，表示ACM有多少种不同的走法。

具体输出见样例。

样例输入

22 2.w.w3 3...w..... 样例输出

03 代码： #include
    
      int main() {
      int n, m, t, i, j, dp[15][15];     char p[15][15];     scanf("%d", &t);     while(t--)     {
          scanf("%d%d", &n, &m);         for(i = 0; i < n; i++)             scanf("%s", p[i]); // 用字符串的形式输入，因为中间会有换行，还方便         for(i = 0; i <= n; i++)             dp[i][0] = 0;         for(j = 0; j <= m; j++)             dp[0][j] = 0;   //清零         dp[0][1] = 1;   //没有这一步，没有ac         if(p[0][0] == 'w' || p[n-1][m-1] == 'w')         {
              printf("0\n");             continue;  //第一步或最后一步是‘w’，没有走法         }         for(i = 1; i <= n; i++)         {
              for(j = 1; j <= m; j++)             {
                  if(p[i-1][j-1] == 'w')  //  代码的点：dp下标和地图p下标不是对应的。横竖坐标都错了一个，目的是方便dp加数                     dp[i][j] = 0;  //w，即使有别的点到这一步，这一步也到不了其他地方，所以置零                 else                     dp[i][j] = dp[i-1][j] + dp[i][j-1];  //这一点只能由它左边的或上边的点到，所以走法，dp，是它们两个的和             }         }         printf("%d\n", dp[n][m]);  // 输出最后一个的dp，不同走法     }     return 0; } 还可以用递归来写：
    

#include<stdio.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 18

int ans, n, m;

char p[N][N];

void f(int x, int y)

{

    if(x < 0 || x >= n || y < 0 || y >= m)

        return ;

    else if(x ==n-1 && y == m-1 && p[x][y] == '.')

    {

        ans++;

        return;

    }

    else if(p[x][y] == '.')

    {

        f(x, y+1);

        f(x+1, y);

    }

    else if(p[x][y] == 'w')

        return ;

}

int main()

{

    int t, i;

    scanf("%d ", &t);

    while(t--)

    {

        scanf("%d%d", &n, &m);

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

            scanf("%s", p[i]);

        ans = 0;

        f(0, 0);

        printf("%d\n", ans);

    }

    return 0;

}

之前同学一直都有说我，把worm那题：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=31179，弄明白，这题肯定会，我现在也这么觉着。

但是，之前worm我也是明白了的啊，对于自己也是够了

worm代码：

#include
    
     #include
     
      #define maxn 105 int dp[maxn][maxn]; int main() { int i, j, n, p, m, t; while(scanf("%d%d%d%d", &n, &p, &m, &t) != EOF) { memset(dp, 0, sizeof(dp)); dp[0][p] = 1; for(i = 1; i <= m; i++) for(j = 1; j <= n; j++) dp[i][j] += dp[i-1][j-1] + dp[i-1][j+1]; printf("%d\n", dp[m][t]); } return 0; } 相对worm，这题没有出现自己觉着代码一样，ac不了的情况=·=||
     
    

这一篇博客真不容易

浏览器又想坏事，先提交了（投诉火狐==|| 试试谷歌orzZ