• <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>
            隨筆 - 62  文章 - 96  trackbacks - 0
            <2006年8月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(7)

            隨筆分類(66)

            隨筆檔案(62)

            文章分類(31)

            文章檔案(32)

            友情鏈接

            最新隨筆

            積分與排名

            • 積分 - 235812
            • 排名 - 108

            最新評論

            閱讀排行榜

            評論排行榜

            今天做出了第一題深度優(yōu)先搜索題。
            至此對廣度和深度有了一個基本的了解。
            學ACM總算學到了一點非暴力解決問題的方法。
            Problem Id:1154??User Id:beyonlin_SCUT
            Memory:32K??Time:155MS
            Language:C++??Result:Accepted
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1154

            LETTERS
            Time Limit:1000MS? Memory Limit:10000K
            Total Submit:694 Accepted:334

            Description
            A single-player game is played on a rectangular board divided in R rows and C columns. There is a single uppercase
            letter (A-Z) written in every position in the board.
            Before the begging of the game there is a figure in the upper-left corner of the board (first row, first column). In every move, a player can move the figure to the one of the adjacent positions (up, down,left or right). Only constraint is that
            a figure cannot visit a position marked with the same letter twice.
            The goal of the game is to play as many moves as possible.
            Write a program that will calculate the maximal number of positions in the board the figure can visit in a single game.

            Input
            The first line of the input contains two integers R and C, separated by a single blank character, 1 <= R, S <= 20.
            The following R lines contain S characters each. Each line represents one row in the board.

            Output
            The first and only line of the output should contain the maximal number of position in the board the figure can visit.

            Sample Input

            3 6
            HFDFFB
            AJHGDH
            DGAGEH

            Sample Output

            6

            我的程序:
            #include<cstdio> #include<stack> using namespace std; struct node { int row; int col; int dire; }; char p[30][30]; char flag[30]; int incr[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int main() { int i,row,col; scanf("%d%d",&row,&col); getchar(); char ch[30]; for(i=1;i<=row;i++) { gets(ch); int j; for(j=1;j<=col;j++) p[i][j]=ch[j-1]; } //初始化,外加一層 for(i=0;i<=col+1;i++) { p[0][i]='0'; p[row+1][i]='0'; } for(i=0;i<=row+1;i++) { p[i][0]='0'; p[i][col+1]='0'; } int Maxmove=0;//最大步數(shù) stack<node>path;
            ????????//棧初始化 int r=1,c=1,dire=0,f=0,move=1; node in; in.row=r; in.col=c; in.dire=dire; path.push(in); flag[f++]=p[r][c]; while(!path.empty()) { if(dire<4) { int r2=r+incr[dire][0]; int c2=c+incr[dire][1]; bool b=true; for(int k=0;k<f;k++)//搜索是否已訪問或路不通 { if(flag[k]==p[r2][c2] || p[r2][c2]=='0') { dire++; b=false; break; } } if(b)//路通 { node in; in.row=r2; in.col=c2; in.dire=dire; path.push(in);//進棧 move++; flag[f++]=p[r2][c2];//標志已訪問 r=r2; c=c2; dire=0; } } else//找到一個解 { if(move>Maxmove) Maxmove=move; move--; dire=path.top().dire+1; //回溯,去除訪問標志 path.pop(); flag[--f]='\0'; if(!path.empty()) { r=path.top().row; c=path.top().col; } } } printf("%d\n",Maxmove); return 0; }

            posted on 2006-08-28 01:23 beyonlin 閱讀(854) 評論(0)  編輯 收藏 引用 所屬分類: acm之路
            国内精品久久国产大陆| 久久人人爽人人爽AV片| 久久久久亚洲AV片无码下载蜜桃| 久久一区二区三区99| 日韩AV无码久久一区二区| 99久久国产热无码精品免费久久久久| 久久国产乱子伦精品免费午夜| 亚洲国产欧美国产综合久久| 久久91精品久久91综合| 久久天天躁狠狠躁夜夜2020老熟妇| 国产精品久久久久久久app | 浪潮AV色综合久久天堂| 国产免费久久精品99久久| 久久久久亚洲AV成人网人人网站 | 久久人与动人物a级毛片| 国产V亚洲V天堂无码久久久| 久久影院午夜理论片无码| 久久九九精品99国产精品| 久久午夜福利电影| 久久亚洲国产欧洲精品一| 亚洲中文字幕无码久久精品1 | 青青青青久久精品国产h久久精品五福影院1421 | 免费观看久久精彩视频| 亚洲∧v久久久无码精品| 久久伊人五月天论坛| 久久久久噜噜噜亚洲熟女综合| 国产精品99久久久久久人| 天天躁日日躁狠狠久久| 久久人人爽人人人人片av| 综合久久一区二区三区| 亚洲国产一成久久精品国产成人综合 | 欧美精品一区二区精品久久| 久久精品国产亚洲AV嫖农村妇女 | 99久久99久久精品免费看蜜桃| 久久久久久久波多野结衣高潮| 亚洲国产精品无码久久青草| 欧美大战日韩91综合一区婷婷久久青草 | 精品久久久无码中文字幕天天 | 久久电影网一区| 久久香蕉国产线看观看乱码| 中文精品久久久久国产网址|