• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            posts - 106,  comments - 32,  trackbacks - 0

            How many ways

            Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 474    Accepted Submission(s): 325


            Problem Description
            這是一個簡單的生存游戲,你控制一個機器人從一個棋盤的起始點(1,1)走到棋盤的終點(n,m)。游戲的規則描述如下:
            1.機器人一開始在棋盤的起始點并有起始點所標有的能量。
            2.機器人只能向右或者向下走,并且每走一步消耗一單位能量。
            3.機器人不能在原地停留。
            4.當機器人選擇了一條可行路徑后,當他走到這條路徑的終點時,他將只有終點所標記的能量。

            如上圖,機器人一開始在(1,1)點,并擁有4單位能量,藍色方塊表示他所能到達的點,如果他在這次路徑選擇中選擇的終點是(2,4)

            點,當他到達(2,4)點時將擁有1單位的能量,并開始下一次路徑選擇,直到到達(6,6)點。
            我們的問題是機器人有多少種方式從起點走到終點。這可能是一個很大的數,輸出的結果對10000取模。
             

            Input
            第一行輸入一個整數T,表示數據的組數。
            對于每一組數據第一行輸入兩個整數n,m(1 <= n,m <= 100)。表示棋盤的大小。接下來輸入n行,每行m個整數e(0 <= e < 20)。
             



            #include<stdio.h>
            #include
            <string.h>
            int map[101][101],n,m,ans[101][101];//存在當前節點可以到達終點的路數
            int  DFS(int x,int y)
            {
                
            if (x==n&&y==m)return 1;
                
            if (ans[x][y]!=-1)return ans[x][y];
                
            int num=0,i,j,t=map[x][y];
                
            for (i=0;i<=t;i++)
                    
            for (j=0;j+i<=t;j++)
                    {
                        
            if (!(i==0&&j==0)&&x+i<=n&&y+j<=m)//!(i==0&&j==0) 防止原地不動
                        {
                            num
            +=DFS(x+i,y+j);
                            num
            %=10000;
                        }
                    }
                ans[x][y]
            =num;
                
            return num;
            }
            int main()
            {
                
            int cas,i,j;
                scanf(
            "%d",&cas);
                
            while (cas--&&scanf("%d %d",&n,&m))
                {
                    memset(ans,
            -1,sizeof(ans));
                    
            for (i=1;i<=n;i++)
                        
            for (j=1;j<=m;j++)
                            scanf(
            "%d",&map[i][j]);
                    printf(
            "%d\n",DFS(1,1));
                }
                
            return 0;
            }

            posted on 2010-08-15 17:39 付翔 閱讀(403) 評論(0)  編輯 收藏 引用 所屬分類: ACM 水題

            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            午夜肉伦伦影院久久精品免费看国产一区二区三区 | 热re99久久6国产精品免费| 性做久久久久久久久老女人 | 丁香色欲久久久久久综合网| 91精品国产综合久久婷婷| 很黄很污的网站久久mimi色 | 国产一区二区精品久久| 色婷婷久久综合中文久久一本| 亚洲精品无码久久千人斩| 99久久亚洲综合精品网站| 精品多毛少妇人妻AV免费久久 | 久久久久99精品成人片欧美| 一级做a爱片久久毛片| 久久精品国产亚洲AV蜜臀色欲 | 97超级碰碰碰久久久久| 久久综合色之久久综合| 嫩草影院久久99| 久久婷婷五月综合色奶水99啪| 久久精品国产只有精品66| 国内精品久久久久影院一蜜桃| 一本久久综合亚洲鲁鲁五月天| 国内精品九九久久久精品| 国产成人精品三上悠亚久久| 手机看片久久高清国产日韩| 亚洲综合久久综合激情久久| 嫩草伊人久久精品少妇AV| 国内精品久久久久影院薰衣草 | 久久久这里只有精品加勒比| 久久99久久成人免费播放| 青青青青久久精品国产 | 色诱久久av| 久久综合偷偷噜噜噜色| 久久久久国产精品嫩草影院| 99久久精品国产综合一区| 久久亚洲高清观看| 情人伊人久久综合亚洲| 久久久久久A亚洲欧洲AV冫 | 色欲久久久天天天综合网| 无码AV中文字幕久久专区| 午夜精品久久久久久99热| 国内精品久久久人妻中文字幕|