原题:hdoj 1010 原题大意又是走迷宫的题目,不过这题有点不一样,因为要求狗狗要在T时刻恰好走到D处. 算法分析明显dfs,不过直接深搜很快就会发现超时了,所以一定得剪枝,百度了下,除了剩余最短步数大于剩余时间外还有一个奇偶剪枝. 程序代码#include <iostream> #include <math.h> #include <memory.h> using namespace std; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int n,m,t;//对应N,M,T char maze[7][7];//迷宫 bool used[7][7]; struct Point{ int x,y; }; Point start,door; int flag; void dfs(int x,int y,int time) { if(flag) return ;//如果找到就return!否则容易超时 if(time>t) return; if(x==doo ...

原题:hdoj 1252 原题大意三个棋子,通过棋盘移到同一点,只有当标线的颜色与两个对手棋子之间的标线颜色一样时,棋子才能移动.求出最少移动的步数. 算法分析广搜计算最小步数.结点本身自循环,是有边的,广搜时要排除 程序代码#include <stdio.h> #include <memory.h> #include <ctype.h> int main() { char g[51][51];//无向图中边的颜色 unsigned int step[51][51][51];//棋子到达不同位置是所走的步骤 struct str{ char a,b,c; }list[51*51*51];//广搜的链表 int i,j; int n;//无向图的结点数 int a,b,c;//三个棋子的起始位置 int flag;//能否实现目标的标志 while(scanf("%d",&n)&&n) { scan ...

原题:Zoj 1101 题目大意游戏开始时，他们各自将自己的赌注盖住,同时任何两个赌徒的赌注是不同的,如果其中一个赌徒没有钱了,他可以借一些筹码,但是他的赌注就是负数了.假设,他们的赌注都是整数.然后他们揭开所有的赌注.赢家为：他的赌注是其他三个人的赌注的综合.如果赢家不止一家,那么拥有最大赌注的人是赢家. 算法分析对于此题，求三个数n1,n2,n3使其之和为另一个数字n.如果存在多种情况,求n值最大的一个.所以首先将所有的数字从小到大排列,从后向前求解,这样就保证求得的第一个赢家为最大值.剩下的三个数枚举求得. 程序代码#include <iostream> #include <algorithm> using namespace std; int n; int winner; int bet[1000]; int binsearch(int k,int val) { int left,right,mid; left=k+1; right=n-1; while(left<=right) { mid= ...

原题:hdoj 1044 原题大意在能走出迷宫的情况下,收集最大价值的珠宝,’*’是墻,’.’表示可以走的空地,’@’表示起点,’<’表示终点,’A-J’用来表示各种价值的珠宝. 算法分析这题百度了下,我能用的方法就是bfs加dfs,先用bfs算出出口,入口,珠宝之间的两两最短距离,然后再用dfs遍历每条从起点到终点的路径. 注意事项这题我一开始交的时候总是超时,后来百度了下,在dfs里加了段代码,作用是如果收集的珠宝已达到所有珠宝价值之和,递归就结束.(这是我第一次超时,下次再出现时要考虑清楚哪里可以缩短时间) 程序代码#include <iostream> #include <queue> #include <memory.h> using namespace std; int W,H,L,M; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; char g[50][50]; int len[12][12];//宝物,出入口的两两距离 int l[50][50];//记录距离 bool used[12] ...

原题:hdoj 1072 原题大意走迷宫,用数组表示迷宫,0表示墻,1表示空房间,2表示起点,3表示终点,4表示可重新设置时间的房间.限时6s,每走一步算1s,走到4房间后可以将时间重新设为6s. 算法分析bfs检索,从2开始,若时间用光后没能走出,输出-1,否则输出最少的步数.注意:当走过任何一个4号房间后,其重新设置时间的功能应当取消,否则走不出来. 程序代码#include <iostream> #include <queue> #include <memory.h> using namespace std; const int N=8; int dx[]={0,0,1,-1};//8个方向 int dy[]={1,-1,0,0}; int labyrinth[N][N];//记录迷宫 int used[N][N];//记录房间4是否被走过 int row,col;//迷宫实际占用的行与列 int flag=0;//能否成功走出的标志 struct Point{ int x,y; int time;//记录剩余时间 ...