PekingUniversityOJ No.1979

这学期一时兴起选修选了个acm课，其实就想补补自己的数据结构和算法，大学前两年下来感觉代码功底不够扎实，希望借此机会巩固加强一下代码能力，算法题我主要以C++来实现，因为自己C++没有系统的学习过，就以练代学吧！

本题是一道很简单的搜索题，也正好是课上刚巩固的内容。这里我使用的是广度优先搜索，单纯因为想练练广搜的算法实现。

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

6 9
….#.
…..#
……
……
……
……
……
#@…#
.#..#.
11 9
.#………
.#.#######.
.#.#…..#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#…….#.
.#########.
………..
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
…@…
###.###
..#.#..
..#.#..
0 0
Sample Output：

45
59
6
13

Source：

Japan 2004 Domestic

//
//  main.cpp
//  PekingOJ
//
//  Created by leo on 2019/10/18.
//  Copyright © 2019 leo. All rights reserved.
//
//

#include <iostream>
#include <queue>
using namespace std;
queue<int> qq;

int countt;
int a[4]={0,0,1,-1};      //a和b数组定义了上下左右“走”的规则 课上老师讲了道例题是象棋马的搜索，只要修改这两个数组即可
int b[4]={1,-1,0,0};
char map[20][20];           //最大是一个20*w20的盘子
bool mp[20][20];            //防止状态重复
bool in(int a,int b,int m,int n)    //判断是否有越界
{
        return (a>=0&&a<=n-1&&b>=0&&b<=m-1);
}
void bfs(int x,int y,int m,int n){      //广度优先搜索主要就借助队列来实现
    qq.push(x);
    qq.push(y);
    int k;
    int x_coordinate,y_coordinate;
    while(!qq.empty())
    {
        x_coordinate=qq.front();
        //std::cout<<x_coordinate<<endl;
        qq.pop();
        y_coordinate=qq.front();
        //std::cout<<y_coordinate<<endl;
        qq.pop();
        countt=countt+1;
        for(k=0;k<4;k++){
            if(map[x_coordinate+a[k]][y_coordinate+b[k]]=='.'&&!mp[x_coordinate+a[k]][y_coordinate+b[k]]&&in(x_coordinate+a[k],y_coordinate+b[k],m,n))
            {
                mp[x_coordinate+a[k]][y_coordinate+b[k]]=true;
                qq.push(x_coordinate+a[k]);
                qq.push(y_coordinate+b[k]);
            }
        }
         
    }
}
int main(int argc, const char * argv[]) {
    int m,n;

    int enter_x=0,enter_y=0;
        
        while(std::cin>>m>>n)
        {

            countt=0;
            if(m==0&&n==0){
                break;
            }
            for(int e=0;e<n;e++)              //初始化用于判重的矩阵
                for(int r=0;r<m;r++)
                    mp[e][r]=false;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    std::cin>>map[i][j];
                    if (map[i][j]=='@'){
                        enter_x=i;
                        enter_y=j;
                        mp[i][j]=true;
                    }
                }
            }
    //std::cout<<enter_x<<enter_y;
    //std::cout<<map[enter_x][enter_y];
        bfs(enter_x,enter_y,m,n);
        std::cout<<countt<<endl;
        }
    return 0;
}

总结

很久没有写算法题了，代码自认为写得就不是很好看，其实中间还有很多可以改变的地方。看过别人写的这道题的代码。不使用单独的判重数组，每次访问到队列中的某个节点后将此节点上的内容改为‘#’，也就没法再次访问了，也是很好的想法。不过我还是倾向去将各个模块分割，重复状态的判断我认为还是在搜索算法里是一个很重要的模块。

coding期间出现的问题

忘记初始化判重数组【一开始我也没写bool in函数】，导致在从第二次及以后的瓦片读取后计算可能会出错（遗留下来的map会影响下一张map）。