HDU-1312题解（DFS）

HDU-1312-DFS

Written by Void-Walker 2020-02-01 09:09:25

1.题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1312

2.题目大意：

有一个矩形房间，房间里有红砖块（‘#’）和黑砖块（‘.’）组成。现在有一个人站在一个@上面，他只能走黑色方块，现在问他最多能经过多少黑色方块。（他的初始位置也算）

3.题目思路：

这道题是一个非常经典的深度优先搜索。我们从他的初始位置开始搜索：

for(y=;y<hy;y++)

{

    for(x=;x<wx;x++)

    {

        cin>>room[x][y];

        if(room[x][y]=='@')

        {

                    dx=x;

            dy=y;

        }

    }

}

注意，认真读题，我们输入的两个尺寸参数第一个是数列，第二个才是横行，输入的时候要小心。之后，我们获得了初始位置就可以开始DFS了。

void DFS(int dx,int dy)

{

    room[dx][dy]='#';

    num++;

    for(int i=;i<;i++)

    {

        int newx=dx+dirx[i];

        int newy=dy+diry[i];

        if(CHECK(newx,newy) && room[newx][newy]=='.')

        {

            DFS(newx,newy);

        }

    }

}

我们采用了一种非常巧妙的方法，每次搜索到一个点的时候，将这个点统一标记为红点，避免重复搜索。

这里的DFS非常经典，不包含其他拐弯抹角的地方，所以思想难度相对简单。

最后给出完整的代码：

#include<bits/stdc++.h>

using namespace std;

char room[][];

int dirx[]={,,-,};

int diry[]={,,,-};

int i,j;

int wx,hy,num;

bool CHECK(int x,int y)

{

    if(x<wx && x>= && y<hy && y>= ) return true;

    else return false;

}

void DFS(int dx,int dy)

{

    room[dx][dy]='#';

    num++;

    for(int i=;i<;i++)

    {

        int newx=dx+dirx[i];

        int newy=dy+diry[i];

        if(CHECK(newx,newy) && room[newx][newy]=='.')

        {

            DFS(newx,newy);

        }

    }

}

int main()

{

    int x,y,dx,dy;

    while(cin>>wx>>hy)

    {

        if(wx== && hy==)

        {

            break;

        }

        for(y=;y<hy;y++)

        {

            for(x=;x<wx;x++)

            {

                cin>>room[x][y];

                if(room[x][y]=='@')

                {

                    dx=x;

                    dy=y;

                }

            }

        }

        num=;

        DFS(dx,dy);

        cout<<num<<endl;

    }

}

巴特西

HDU-1312题解（DFS）

最新文章

热门文章