• <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)

            友情鏈接

            最新隨筆

            積分與排名

            • 積分 - 235714
            • 排名 - 108

            最新評論

            閱讀排行榜

            評論排行榜

            今天做出了第一題深度優先搜索題。
            至此對廣度和深度有了一個基本的了解。
            學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;//最大步數 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 閱讀(853) 評論(0)  編輯 收藏 引用 所屬分類: acm之路
            久久这里只有精品首页| 国产精品久久久久久久午夜片| 久久久久亚洲AV成人网人人软件| 久久99国产精品久久| 久久成人18免费网站| 久久国产色av免费看| 伊人久久免费视频| 2021国产精品午夜久久| 亚洲国产精品人久久| 久久久久久久亚洲精品| 久久久精品人妻一区二区三区蜜桃| 精品无码久久久久久午夜| 久久亚洲高清观看| 久久久久国产成人精品亚洲午夜| 日韩美女18网站久久精品| 日韩精品久久久久久免费| 很黄很污的网站久久mimi色| 模特私拍国产精品久久| 亚洲午夜久久影院| 亚洲va中文字幕无码久久| 久久精品无码一区二区app| 国内精品久久久久影院一蜜桃| 久久综合偷偷噜噜噜色| 99久久99久久精品国产片果冻| 欧美牲交A欧牲交aⅴ久久| 色偷偷88欧美精品久久久| 久久高清一级毛片| 国产69精品久久久久9999| 国产精品久久久久影院色| 久久久精品2019免费观看| 一本色道久久综合狠狠躁| 色偷偷88欧美精品久久久| 久久久WWW免费人成精品| 999久久久国产精品| 狠狠人妻久久久久久综合| 国产伊人久久| 日本福利片国产午夜久久| segui久久国产精品| 欧美激情精品久久久久| 国产精自产拍久久久久久蜜| 久久亚洲精品视频|