HDU4101-很好的BFS题目(虽然结果是判断输赢)

2024-05-04 19:48
文章标签 题目 bfs 判断 输赢 hdu4101

本文主要是介绍HDU4101-很好的BFS题目(虽然结果是判断输赢),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:题目链接

 

 

题意:题目的意思就是说两个人轮流玩游戏,给你一张地图,这个地图中间有一点-1代表宝藏,Ali and Baba轮流走

路,如果某一个人能够直接走到宝藏的话,那么他就赢了。地图上其它的点0代表空地,数字代表当前地点的石子当

某一人拿石子的时候,他只能拿走一颗。问你谁最后能拿到宝藏;

 

分析:宝藏位于-1的位置,那么如果Ali一开始的时候就可以通过外围的某一点的空地直接经过空地到达宝藏,那么

Ali就赢了,所以我们应该以-1为起点,广搜一次,这样,我们就可以找到可以链接到宝藏的直接路径了(记作区域

A),如果广搜过程中碰见了空地边缘,那么Ali必赢(Ali直接从这里进去就可以了)。如果没有的话,那么到达宝

藏的路线肯定被石子包围住了,那么路径周围的石子当都被移动到只剩1棵时,此时当前选手只能选择打开围墙,那

么他就输了。所以就从外围开始由外向内搜索,如果遇到非A区域的石头,总计和ans加上当前位置的石子数目,如果

遇到的是A区域的石头,总计和ans加上当前位置石子数目-1(必须要留下一个石子,否则对方就赢了),最后求得的

ans也就是Ali能够实施的合法步骤数,根据ans的奇偶性便能得出答案。

 

略麻烦的BFS,狂躁ing.....

 

 

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;int gcd(int  n,int  m)
{if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);
}
int lcm(int n,int m)
{if(n<m) swap(n,m);return n/gcd(n,m)*m;
}
int prime[100];void getPrime();
void bash();
void wzf();
void SG();
int QuickMod(int a, int b, int n);const int maxn = 305;
int mp[maxn][maxn];
bool vis1[maxn][maxn];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool vis[maxn][maxn];int N, M;
int dx, dy;struct node
{int x, y;
};bool bfs1()
{memset(vis1, false, sizeof vis1);queue<node> Q;node t;t.x = dx, t.y = dy;vis1[dy][dx] = true;Q.push(t);while(!Q.empty()){node cur = Q.front();Q.pop();int cx = cur.x;int cy = cur.y;for(int i = 0; i < 4; i++){int nx = cx + dir[i][0];int ny = cy + dir[i][1];if(nx > 0 && nx <= M && ny > 0 && ny <= N){if(!vis1[ny][nx]){vis1[ny][nx] = true;if(mp[ny][nx] == 0){t.x = nx, t.y = ny;Q.push(t);}}}elsereturn true;}}return false;
}int bfs2()
{memset(vis, false, sizeof vis);int ans = 0;queue<node> Q;node s, t;s.x = 0, s.y = 0;vis[0][0] = true;Q.push(s);while(!Q.empty()){node cur = Q.front();Q.pop();int cx = cur.x;int cy = cur.y;for(int i = 0; i < 4; i++){int nx = cx + dir[i][0];int ny = cy + dir[i][1];if(nx >= 0 && nx <= M + 1 && ny >= 0 && ny <= N + 1){if(!vis[ny][nx]){vis[ny][nx] = true;if(!vis1[ny][nx]){ans += mp[ny][nx];t.x = nx, t.y = ny;Q.push(t);}else if(vis1[ny][nx] && mp[ny][nx] > 0){ans += mp[ny][nx] - 1;}}}}}return ans;
}int main()
{while(scanf("%d %d", &N, &M) != EOF){memset(mp, 0, sizeof mp);for(int i = 1; i <= N; i++){for(int j = 1; j <= M; j++){scanf("%d", &mp[i][j]);if(mp[i][j] == -1)dx = j, dy = i;}}if(bfs1()){puts("Ali Win");continue;}int ans = bfs2();if(ans & 1)puts("Ali Win");elseputs("Baba Win");}return 0;
}
int QuickMod(int  a,int b,int n)
{int r = 1;while(b){if(b&1)r = (r*a)%n;a = (a*a)%n;b >>= 1;}return r;
}void getPrime()
{memset(prime, 0, sizeof(prime));prime[0] = 1;prime[1] = 1;for(int i = 2; i < N; ++i){if(prime[i] == 0){for(int j = i+i; j < N; j+=i)prime[j] = 1;}}
}void bash(int n, int m)
{if(n%(m+1) != 0)printf("1\n");elseprintf("0\n");
}void wzf(int n, int m)
{if(n > m)swap(n, m);int k = m-n;int a = (k * (1.0 + sqrt(5.0))/2.0);if(a == n)printf("0\n");elseprintf("1\n");
}int numsg[100];
void SG(int n)
{int sum = 0;for(int i=0; i < n; i++){scanf("%d",&numsg[i]);sum ^= numsg[i];}if(sum == 0)printf("No\n");else{printf("Yes\n");for(int i = 0; i < n; i++){int s = sum ^ numsg[i];if(s < numsg[i])printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子}}
}


 

这篇关于HDU4101-很好的BFS题目(虽然结果是判断输赢)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959974

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop