• <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之路
            久久综合九色综合网站| 久久精品水蜜桃av综合天堂| 久久精品99无色码中文字幕| 国产精品久久久久久久午夜片| 久久精品国产91久久麻豆自制 | 国产精品久久久久久影院 | 亚洲精品美女久久久久99小说 | 久久久久国产精品嫩草影院| 色综合久久中文字幕综合网| 久久久亚洲裙底偷窥综合 | 思思久久99热免费精品6| 久久精品国产亚洲AV久| 国产精品久久精品| 久久天天躁夜夜躁狠狠躁2022| 久久成人国产精品| 亚洲精品WWW久久久久久| 久久国产精品99精品国产| 久久国产精品无码网站| 精品久久久久久亚洲精品| 久久精品18| 成人a毛片久久免费播放| 久久久久久免费视频| 久久精品www| 亚洲av伊人久久综合密臀性色| 精品欧美一区二区三区久久久| 中文字幕人妻色偷偷久久| 久久人妻少妇嫩草AV蜜桃| 99久久这里只有精品| 日本WV一本一道久久香蕉| 国产高潮国产高潮久久久91 | 久久精品国产亚洲精品| 久久精品亚洲中文字幕无码麻豆| 中文字幕精品无码久久久久久3D日动漫 | 精品一区二区久久| 久久超乳爆乳中文字幕| 久久综合久久自在自线精品自| 天天影视色香欲综合久久| 久久精品国产亚洲Aⅴ香蕉| 精品一久久香蕉国产线看播放| 国产亚洲美女精品久久久久狼| 久久丫精品国产亚洲av|