首页 > 代码库 > POJ_1979_dfs

POJ_1979_dfs

题目描述:

  每组数据给你一张字符的图,‘@‘代表起点,‘.‘代表可走的路,‘#‘代表墙,求从起点出发,可到达的位置的数量,包括起点。

思路:

  dfs基础题,从起始点开始,每一次所在的点,只要不出界并且字符为‘@‘或‘.‘,则把这个点的字符改为一个标志,再向四周扩散。如果出了边界或者遇到‘#‘,则这条路到尽头。

  最后只要遍历整张图,统计标志的数量即可。

  好像有点不道德,直接把原图修改了= =

 

#include<iostream>#include<cstdio>#include<string>using namespace std;string a[25];int H,W,dir[][2] ={{0,-1},{0,1},{1,0},{-1,0}};void dfs(int x,int y){    if(x < 0 || x >= H || y < 0 || y >= W)  return;    if(a[x][y] == . || a[x][y] == @)    {        a[x][y] = 1;        for(int i = 0;i < 4;i++)        {            int xx = x+dir[i][0],yy = y+dir[i][1];            dfs(xx,yy);        }    }}int main(){    while(cin >> W >> H && W && H)    {        int beginx,beginy;        for(int i = 0;i < H;i++)        {            cin >> a[i];        }        for(int i = 0;i < H;i++)        {            for(int j = 0;j < W;j++)            {                if(a[i][j] == @)                {                    beginx = i;                    beginy = j;                }            }        }        dfs(beginx,beginy);        int sum = 0;        for(int i = 0;i < H;i++)        {            for(int j = 0;j < W;j++)            {                if(a[i][j] == 1)    sum++;            }        }        cout << sum << endl;    }    return 0;}

 

POJ_1979_dfs