poj1979 Red and Black 简单深搜

题目描述

Red and Black
大意是只能走周围的4个相邻点，只能走黑色点(即‘.’)，不能走红色点(即‘#’)
输出最多可以走多少个不同的黑色点(起始点也算)

解题思路:
DFS
往四个方向走，走过的点标记一下
碰到红色点或者越界或者标记过的点，是DFS的终止条件

sample input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

sample output

45
59
6
13

代码:

#include<iostream>
#include<string>
using namespace std;
char map[21][21];
bool mark[21][21];
int a, b;
int mynext[4][2] = {
    1,0,-1,0,0,1,0,-1
};
int ans = 0;
void DFS(int x, int y) {
    if (x >= a || x < 0 || y < 0 || y >= b || mark[x][y] == true || map[x][y] == '#') {
     return; }mark[x][y] = true;ans++;for (int i = 0; i < 4; i++) {
    int nx = x + mynext[i][0];int ny = y + mynext[i][1];DFS(nx, ny);}
}
int main() {
    while (cin>>b>>a) {
    int initx, inity;if (a == 0 && b == 0) {
     break; }for (int i = 0; i < a; i++) {
    for (int j = 0; j < b; j++) {
    cin >> map[i][j];mark[i][j] = false;if (map[i][j] == '@') {
    initx = i; inity = j;}}}DFS(initx, inity);cout << ans << endl;ans = 0;}
}