HDU 1312 RED AND BLACK

题目链接：HDU 1312 【RED AND BLACK】

思路

       简单搜索，输入数据时，找出起点位置，然后从七点位置开始搜素能到达的所有位置并记录，使用check()函数判断当前位置可以走吗，可以走就把当前位置放入队列中，并将当前位置修改为非黑色位置，防止重复进入。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 30;

int n, m, startx, starty, dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
char mp[N][N];

void init() {
  startx = starty = 0;
  memset(mp, 0, sizeof mp);
}

// 判断当前位置是否合法
bool check(int x, int y) {
  if (x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] == '.')
    return true;
  else
    return false;
}

// 搜索所有结果
int bfs(int x, int y) {
  int countTitle = 1;

  // 初始化队列
  queue<pair<int, int>> q;
  q.push({x, y});

  while (!q.empty()) {
    // 取出栈顶数据
    pair<int, int> d = q.front();
    q.pop();
    // 判断栈顶元素四个方向是否可以走
    for (int i = 0; i < 4; i++) {
      pair<int, int> dd = d;
      dd.first += dir[i][0], dd.second += dir[i][1];
      // 当前方向可以走的时候，加入队列，并将当前节点标记为非黑色节点，防止重复走
      if (check(dd.first, dd.second) == true) {
        q.push(dd);
        mp[dd.first][dd.second] = '@';
        countTitle++;
      }
    }
  }
  return countTitle;
}

int main() {
  while (cin >> m >> n) {
    // 停止输入条件
    if (n == m && n == 0)
      break;
    // 初始化所有数据
    init();
    // 输入数据并找出起点
    for (int i = 1; i <= n; i++) {
      cin >> (mp[i] + 1);
      for (int j = 1; j <= m; j++) {
        if (mp[i][j] == '@') {
          startx = i, starty = j;
        }
      }
    }
    // 搜索并输出
    cout << bfs(startx, starty) << endl;
  }
  return 0;
}