DFS做法-问题 B: DFS or BFS?

Serwa ·

更新时间:2024-09-20

· 727 次阅读

使用DFS的做法
AC代码

#include 
#include 
using namespace std;
struct Node {
	int x, y;
	//存放石头的位置的集合
	vector stones;
} startNode, tempNode, stone;
char matrix[8][8];
int n;
bool isEnd = false;
bool isWin = false;
void input() {
	for(int i= 0; i < 8; i++) {
		for(int j = 0; j < 8; j++) {
			scanf("%c", &matrix[i][j]);
		}
		getchar();
	}
}
//把石头的位置存入startNode.stones
void findStones() {
	if(!startNode.stones.empty()) {
		startNode.stones.clear();
	}
	for(int i= 0; i < 8; i++) {
		for(int j = 0; j < 8; j++) {
			if(matrix[i][j] == 'S') {
				stone.x = i;
				stone.y = j;
				startNode.stones.push_back(stone);
			}
		}
	}
}
int X[] = {0, 0, 0, 1, -1, 1, 1, -1, -1};
int Y[] = {0, 1, -1, 0, 0, 1, -1, 1, -1};
bool check(Node &node) {
	if(node.x = 8 || node.y = 8) return false;
	for(vector::iterator it = node.stones.begin(); it != node.stones.end(); it++) {
		if(node.x == (*it).x && node.y == (*it).y)  return false;
		(*it).x++;
		//掉出矩阵，删除
		if((*it).x >= 8) {
			node.stones.erase(it);
		}
		//石头压住，结束
		if((*it).x == node.x && (*it).y == node.y) return false;
		//有个陷阱，就是遍历集合的时候还删除元素的话，会出错！增加个判断就能解决
		if(it == node.stones.end()) break;
	}
	return true;
}
void DFS(Node node) {
	if(node.stones.size() == 0) {
		isEnd = true;
		isWin = true;
		return;
	}
	for(int i = 0; i < 9; i++) {
		int newX = node.x + X[i];
		int newY = node.y + Y[i];
		tempNode.x = newX;
		tempNode.y = newY;
		tempNode.stones = node.stones;
		if(check(tempNode) && isEnd == false) {
			DFS(tempNode);
		}
	}
}
int main() {
	startNode.x = 7;
	startNode.y = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		isEnd = false;
		isWin = false;
		getchar();
		input();
		findStones();
		DFS(startNode);
		if(isWin) {
			printf("Case #%d: Yes\n", i);
		} else {
			printf("Case #%d: No\n", i);
		}
	}
	return 0;
}