• <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年4月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            常用鏈接

            留言簿(7)

            隨筆分類(66)

            隨筆檔案(62)

            文章分類(31)

            文章檔案(32)

            友情鏈接

            最新隨筆

            積分與排名

            • 積分 - 235796
            • 排名 - 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之路
            国产精品狼人久久久久影院| 香港aa三级久久三级老师2021国产三级精品三级在| 要久久爱在线免费观看| 欧美午夜精品久久久久久浪潮| 日韩中文久久| 久久精品国产精品青草| 久久久久久久国产免费看| 一本一本久久A久久综合精品| 国产美女久久精品香蕉69| 欧美激情精品久久久久久| 日产精品久久久一区二区| 久久久精品波多野结衣| 亚洲va久久久噜噜噜久久| 久久播电影网| 久久久精品午夜免费不卡| 久久久SS麻豆欧美国产日韩| 久久精品这里热有精品| 久久综合九色欧美综合狠狠| 亚洲国产精品婷婷久久| 色婷婷综合久久久久中文一区二区| 香蕉久久一区二区不卡无毒影院 | 亚洲精品国产美女久久久| 久久国产精品一区| 九九99精品久久久久久| 看久久久久久a级毛片| 一本大道久久香蕉成人网| 久久成人国产精品一区二区| 精品午夜久久福利大片| 97久久超碰成人精品网站| 亚洲午夜久久久影院| 亚洲综合久久久| 日韩欧美亚洲国产精品字幕久久久 | 精品久久久久久国产牛牛app | 久久国产美女免费观看精品| 国产亚洲美女精品久久久久狼| 欧美丰满熟妇BBB久久久| 久久综合久久自在自线精品自| 中文精品久久久久人妻不卡| 婷婷伊人久久大香线蕉AV| 国产美女亚洲精品久久久综合| 久久亚洲AV成人无码软件|