站外DFS & BFS搜索模板题求助
  • 板块学术版
  • 楼主uFTvL9
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/8/10 21:18
  • 上次更新2023/10/27 16:02:37
查看原帖
站外DFS & BFS搜索模板题求助
411963
uFTvL9楼主2022/8/10 21:18

原题:【HDU1312:Red and Black】 http://59.61.214.20:3000/contest/418/problem/3

#include <bits/stdc++.h>
#define elif else if
using namespace std;
inline void init();
//var:(main)
int h, w, x, y;
bool a[52][52];
int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
char ch;
int ans;

inline void DFS(int x, int y) {
	a[x][y] = false;
	ans++;
	for(int i = 1; i <= 4; i++)
		if(a[x + dx[i]][y + dy[i]])
			DFS(x + dx[i], y + dy[i]);
}

int main() {
	init();
	cin >> h >> w;
	for(int i = 1; i <= w; i++) {
		for(int j = 1; j <= h; j++) {
			ch = getchar();
			if(ch == '.') a[i][j] = true;
			elif(ch == '@') {
				x = i;
				y = j;
				a[i][j] = true;
			}
		}
		getchar();
	}
	DFS(x, y);
	cout << ans << '\n';
	return 0;
}

inline void init() {
	freopen("tile.in", "r", stdin);
	freopen("tile.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

#include <bits/stdc++.h>
#define elif else if
using namespace std;
inline void init();
//var:(main)
int h, w, x, y;
bool a[52][52];
int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
char ch;
queue<int> qx, qy;
int ans;

inline int BFS() {
	qx.push(x);
	qy.push(y);
	while(!qx.empty() and !qy.empty()) {
		for(int i = 1; i <= 4; i++) {
			x = qx.front() + dx[i];
			y = qy.front() + dy[i];
			if(a[x][y]) {
				ans++;
				qx.push(x);
				qy.push(y);
				a[x][y] = false;
			}
		}
		qx.pop();
		qy.pop();
	}
	return ans;
}

int main() {
	init();
	cin >> h >> w;
	for(int i = 1; i <= w; i++) {
		for(int j = 1; j <= h; j++) {
			ch = getchar();
			if(ch == '.') a[i][j] = true;
			elif(ch == '@') {
				x = i;
				y = j;
				a[i][j] = false;
			}
		}
		getchar();
	}
	cout << BFS() + 1 << '\n';
	return 0;
}

inline void init() {
	freopen("tile.in", "r", stdin);
	freopen("tile.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

两段程序都有问题,不知道为啥。。

2022/8/10 21:18
加载中...