本文主要是介绍10557 - XYZZY（dfs + bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：10557 - XYZZY
题目大意：就是一款游戏，冒险本来的能量是100，每进一间屋子就可以把屋子里的能量占为己有，但是屋子能量有正有负，然后给起点终点，看能否成功的到达终点。并且一间屋子可以重复进去多次。
解题思路：刚开始想用dfs， 但是题目里面会有环，会出现死循环，一直没想到思路。后来看了别人的代码。才发现可以巧妙的用dfs和bfs。
bfs（）是用来只寻找是否有到达终点的通道。
dfs（）是用来模拟冒险的，一间房间可能会被进去多次，这时就需要判断第二次是，是否比前一次要多，如果是的话，就说明可以通过这条路来累计能量，这样就可以过关。如果比原来的要少，就要判断别的路径是否可能。如果中途能量不足就直接out了。
#include<stdio.h>
#include<string.h>
const int N = 105;
int n, room[N][N], v[N], visit[N];
int energy[N], flag;
int q[N * N];int bfs(int x) {memset(visit, 0, sizeof(visit));memset(q, 0, sizeof(q));int front = 0; int rear = 0;q[rear++] = x;visit[x] = 1;while(front < rear) {x = q[front++];for(int i = 1; i <= n; i++) {if(room[x][i] && !visit[i]) {visit[i] = 1;if(i == n)return 1;q[rear++] = i;} }}return 0;
}void dfs(int x, int e) {if(x == n) {flag = 1;return;}for(int i = 1; i <= n; i++) {if(room[x][i] && !flag && e + v[i] > 0) {if(!energy[i] ) {energy[i] = e + v[i];dfs(i, e + v[i]);}else if(energy[i] < e + v[i] && bfs(i))flag = 1;}}}int main() {while(scanf("%d", &n) , n != -1) {int i, j, m, num;memset(room, 0, sizeof(room));memset(v, 0, sizeof(v));memset(energy, 0, sizeof(energy));for(i = 1; i <= n; i++) {scanf("%d%d", &v[i], &num);for(j = 1; j <= num; j++) {scanf("%d", &m);room[i][m] = 1;} }flag = 0;energy[1] = 100;dfs(1, 100);if(flag)printf("winnable\n");elseprintf("hopeless\n");}return 0;
}
这题一直卡着，主要在审题不清，起点终点明明交代清楚了，竟然没看到，按照自己的想法来找起点，结果出错了。
这篇关于10557 - XYZZY（dfs + bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
