获取中...

-

Just a minute...

  • 原题目:
    Description
    There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
    Write a program to count the number of black tiles which he can reach by repeating the moves described above.
    Input
    The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
    There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
    ‘.’ - a black tile
    ‘#’ - a red tile
    ‘@’ - a man on a black tile(appears exactly once in a data set)
    The end of the input is indicated by a line consisting of two zeros.
    Output

    For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

    Sample Input

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    6 9
    ....#.
    .....#
    ......
    ......
    ......
    ......
    ......
    #@...#
    .#..#.
    11 9
    .#.........
    .#.#######.
    .#.#.....#.
    .#.#.###.#.
    .#.#..@#.#.
    .#.#####.#.
    .#.......#.
    .#########.
    ...........
    11 6
    ..#..#..#..
    ..#..#..#..
    ..#..#..###
    ..#..#..#@.
    ..#..#..#..
    ..#..#..#..
    7 7
    ..#.#..
    ..#.#..
    ###.###
    ...@...
    ###.###
    ..#.#..
    ..#.#..
    0 0

    Sample Output

    1
    2
    3
    4
    45
    59
    6
    13
  • 题目大意:
    给出一个w列和h行的方阵,方阵中有’.’,’#’和‘@’。其中’.’是可以移动的地方,’#’是红色的砖,是不可以移动的地 方,‘@’是最初人的地点就(图的入口),人可以上下左右移动,以0 0 为结束。
    要求输出人可以移动的砖的个数。该题利用搜索。

    注意:
    先输入w,然后输入h,但是w是列数,h是行数。

  • 代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    #include<iostream>
    #include<cstring>
    using namespace std;

    void dfs(int x,int y);
    int w,h,tmp=0;

    char ma[100][100];
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    int main(){
    while(cin>>h>>w){
    if(w==0&&h==0) break;
    memset(ma,'0',sizeof(ma));
    int ax,ay;
    for(int i=0;i<w;i++){
    for(int j=0;j<h;j++){
    cin>>ma[i][j];
    if(ma[i][j]=='@'){
    ax=i;
    ay=j;
    }
    }
    }
    tmp=0;
    dfs(ax,ay);
    cout<<tmp<<endl;
    }
    return 0;
    }

    void dfs(int x,int y){
    ma[x][y]='#';
    tmp++;
    for(int i=0;i<4;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(ma[nx][ny]=='.'&&nx>=0&&nx<w&&ny>=0&&ny<h&&ma[nx][ny]=='.'){
    dfs(nx,ny);
    }
    }
    }
    Select Code
    #include<iostream>
    #include<cstring>
    using namespace std;

    void dfs(int x,int y);
    int w,h,tmp=0;

    char ma[100][100];
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    int main(){
    while(cin>>h>>w){
    if(w==0&&h==0) break;
    memset(ma,'0',sizeof(ma));
    int ax,ay;
    for(int i=0;i<w;i++){
    for(int j=0;j<h;j++){
    cin>>ma[i][j];
    if(ma[i][j]=='@'){
    ax=i;
    ay=j;
    }
    }
    }
    tmp=0;
    dfs(ax,ay);
    cout<<tmp<<endl;
    }
    return 0;
    }

    void dfs(int x,int y){
    ma[x][y]='#';
    tmp++;
    for(int i=0;i<4;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(ma[nx][ny]=='.'&&nx>=0&&nx<w&&ny>=0&&ny<h&&ma[nx][ny]=='.'){
    dfs(nx,ny);
    }
    }
    }

    POJ上不支持bits/stdc++的头文件,很尴尬。

相关文章
评论
分享
  • HDU-1276

    题目描述 某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开...

    HDU-1276
  • Codeforces-787a

    题目传送 题目思路:拓展欧几里德:$$ax+b=cy+d; <=> ax+cy=d-b;$$ 代码: 12345678910111213141516171819202122232425...

    Codeforces-787a
  • HDU-1072

    题目描述:首先输入一个N;代表测试数据的个数;然后每个测试数据的开头第一行输入一个n和一个命令(FIFO或FILO<就是先进先出或先进后出>)然后是该测试数据的n行,每行包括“IN”加一个数字(代表入栈或入队)或者一个“...

    HDU-1072
  • HDU-1222

    题目传送 题目描述: There is a hill with n holes around. The holes are signed from 0 to n-1. A rabbit must hide in one of t...

    HDU-1222
  • HDU - 2072

    题目传送 Sample Input 1you are my friend # Sample Output 14 思路: 利用STL的set,但是需要注意字符串的处理,利用set的特性,建立一个中间字符串变量tmp,把当前单...

    HDU - 2072
  • BASH杂记

    BASH杂记
  • 八大排序算法总结

    直接插入排序算法 概述直接插入排序算法在逻辑上将整体数据分为两部分,一部分是已排序部分,另一部分是待排序部分 。排序的过程是:在待排序部分逐步的拿出一个元素,将其插入到已排序部分中合理的位置 。 适用场景插入排序在对几乎已经排好序的数...

    八大排序算法总结
  • hexo低成本搭建静态网页博客

    引言好多同学有写博客的习惯,也有各大例如csd、简等博客平台。但是这些平台毕竟是盈利平台,无法做到对自己的博客完全掌控,有一丝丝的不爽快。想要DIY一下几乎不可能。在这里推荐同学们自己动手丰衣足食。 准备知识 github最基本的使用...

    hexo低成本搭建静态网页博客
  • CPU信息获取

    准备知识 /proc文件系统是一个伪文件系统,该文件系统中存储着内核控制相关信息,通俗点说就是这个目录是虚拟的,它受内核直接控制,存储与内核控制相关的数据,与其他目录不同的是/proc目录不是真实存储在硬盘中的,它的数据存储在内存...

    CPU信息获取
  • BASH脚本实现素数线性筛

    知识准备 for循环12345678910111213141516171819202122232425for i in `seq 1 10`;do echo ${i}done#执行结果---------12345...

    BASH脚本实现素数线性筛
Please check the parameter of comment in config.yml of hexo-theme-Annie!