HDOJ题目3309 Roll The Cube（BFS）

时间：2022-07-19 08:15:04 其他范文收藏本文下载本文

下面是小编为大家收集的HDOJ题目3309 Roll The Cube（BFS），本文共8篇，仅供参考，欢迎大家阅读，希望可以帮助到有需要的朋友。

篇1：HDOJ 题目2614 Beat（DFS）

Beat

Time Limit: 6000/ MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 837 Accepted Submission(s): 524

Problem Description Zty is a man that always full of enthusiasm. He wants to solve every kind of difficulty ACM problem in the world. And he has a habit that he does not like to solve

a problem that is easy than problem he had solved. Now yifenfei give him n difficulty problems, and tell him their relative time to solve it after solving the other one.

You should help zty to find a order of solving problems to solve more difficulty problem.

You may sure zty first solve the problem 0 by costing 0 minute. Zty always choose cost more or equal time’s problem to solve.

Input The input contains multiple test cases.

Each test case include, first one integer n ( 2< n < 15).express the number of problem.

Than n lines, each line include n integer Tij ( 0<=Tij<10), the i’s row and j’s col integer Tij express after solving the problem i, will cost Tij minute to solve the problem j.

Output For each test case output the maximum number of problem zty can solved.

Sample Input

30 0 01 0 11 0 030 2 21 0 11 1 050 1 2 3 10 0 2 3 10 0 0 3 10 0 0 0 20 0 0 0 0

Sample Output

324HintHint: sample one, as we know zty always solve problem 0 by costing 0 minute. So after solving problem 0, he can choose problem 1 and problem 2, because T01 >=0 and T02>=0. But if zty chooses to solve problem 1, he can not solve problem 2, because T12 < T01. So zty can choose solve the problem 2 second, than solve the problem 1.

Author yifenfei

Source 奋斗的年代

Recommend yifenfei | We have carefully selected several similar problems for you: 1426 2616 1312 1501 2181 ac代码

#include#include#define max(a,b) (a>b?a:b)int map[1010][1010],vis[1010];int ans,n;void dfs(int i,int len,int num){ ans=max(ans,len); if(len==n) return; for(int j=0;j=num) { vis[j]=1; dfs(j,len+1,map[i][j]); vis[j]=0; } } }}int main{ //int n; while(scanf(“%d”,&n)!=EOF) { int i,j; for(i=0;i

篇2：HDOJ题目3309 Roll The Cube（BFS）

Roll The Cube

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 502 Accepted Submission(s): 181

Problem Description This is a simple game.The goal of the game is to roll two balls to two holes each.

'B' -- ball

'H' -- hole

'.' -- land

'*' -- wall

Remember when a ball rolls into a hole, they(the ball and the hole) disappeared, that is , 'H' + 'B' = '.'.

Now you are controlling two balls at the same time.Up, down , left , right --- once one of these keys is pressed, balls exist roll to that direction, for example , you pressed up , two balls both roll up.

A ball will stay where it is if its next point is a wall, and balls can't be overlap.

Your code should give the minimun times you press the keys to achieve the goal.

Input First there's an integer T(T<=100) indicating the case number.

Then T blocks , each block has two integers n , m (n , m <= 22) indicating size of the map.

Then n lines each with m characters.

There'll always be two balls(B) and two holes(H) in a map.

The boundary of the map is always walls(*).

Output The minimum times you press to achieve the goal.

Tell me “Sorry , sir , my poor program fails to get an answer.” if you can never achieve the goal.

Sample Input

46 3****B**B**H**H****4 4*****BB**HH*****4 4*****BH**HB*****5 6*******.BB***.H*H**..*.*******

Sample Output

312Sorry , sir , my poor program fails to get an answer.

Author MadFroG

Source HDOJ Monthly Contest – .02.06

Recommend wxl | We have carefully selected several similar problems for you: 3308 3314 3307 3306 3310 ac代码

#include#include#include#includeusing namespace std;int n,m,vis[25][25][25][25],sx[2],sy[2];char map[25][25];int dx[4]={0,1,0,-1};int dy[4]={1,0,-1,0};struct s{ int x[2],y[2],step,b[2],h[2]; //friend bool operator <(s a,s b) //{ // return a.step>b.step; //}}a,temp;int bfs(){ memset(vis,0,sizeof(vis)); a.x[0]=sx[0],a.x[1]=sx[1]; a.y[0]=sy[0],a.y[1]=sy[1]; a.b[0]=a.b[1]=a.h[0]=a.h[1]=0; vis[sx[0]][sy[0]][sx[1]][sy[1]]=1; a.step=0; //priority_queueq; queueq; q.push(a); while(!q.empty()) { int i,j; //a=q.top(); a=q.front(); q.pop(); for(i=0;i<4;i++) { temp=a; for(j=0;j<2;j++) { if(temp.b[j]) continue; temp.x[j]=a.x[j]+dx[i]; temp.y[j]=a.y[j]+dy[i]; if(map[temp.x[j]][temp.y[j]]=='*') { temp.x[j]=a.x[j]; temp.y[j]=a.y[j]; } }if(vis[temp.x[0]][temp.y[0]][temp.x[1]][temp.y[1]]) continue; if(temp.x[0]==temp.x[1]&&temp.y[0]==temp.y[1]&&temp.b[0]+temp.b[1]==0) continue; vis[temp.x[0]][temp.y[0]][temp.x[1]][temp.y[1]]=1; temp.step=a.step+1; int flag=1; for(j=0;j<2;j++) { int now=map[temp.x[j]][temp.y[j]]; if(now<2&&!temp.h[now]) { temp.h[now]=1; temp.b[j]=1; } if(!temp.b[j]) flag=0; } if(flag) return temp.step; q.push(temp); } } return -1;}int main(){ int t; scanf(“%d”,&t); while(t--) { int i,j; scanf(“%d%d”,&n,&m); int cnt=0,cot=0; for(i=0;i

篇3：HDOJ 题目2303 The Embarrassed Cryptographer（数学）

The Embarrassed Cryptographer

Time Limit: 3000/ MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 563 Accepted Submission(s): 172

Problem Description The young and very promising cryptographer Odd Even has implemented the security module of a large system with thousands of users, which is now in use in his company. The cryptographic keys are created from the product of two primes, and are believed to be secure because there is no known method for factoring such a product effectively.

What Odd Even did not think of, was that both factors in a key should be large, not just their product. It is now possible that some of the users of the system have weak keys. In a desperate attempt not to be fired, Odd Even secretly goes through all the users keys, to check if they are strong enough. He uses his very poweful Atari, and is especially careful when checking his boss' key.

Input The input consists of no more than 20 test cases. Each test case is a line with the integers 4 <= K <= 10100and 2 <= L <= 106. K is the key itself, a product of two primes. L is the wanted minimum size of the factors in the key. The input set is terminated by a case where K = 0 and L = 0.

Output For each number K, if one of its factors are strictly less than the required L, your program should output “BAD p”, where p is the smallest factor in K. Otherwise, it should output “GOOD”. Cases should be separated by a line-break.

Sample Input

143 10143 20667 20667 302573 302573 400 0

Sample Output

GOODBAD 11GOODBAD 23GOODBAD 31

Source NCPC

Recommend zty | We have carefully selected several similar problems for you: 2300 2308 2301 2305 2306 输入一个大数和一个整数k，然后看看那个大大数能不能整除一个素数，要是可以看看那个素数比k大还是小，要是小就输出BAD，并把那个素数输出出来，否则输出GOOD ac代码

#include#includeint is[1000010],prim[10000100],num=0,k;void fun{ int i,j; for(i=2;i<1000010;i++) { if(!is[i]) { prim[num++]=i; for(j=i+i;j<1000010;j+=i) { is[j]=1; } } }}char s[220];int main(){ fun(); while(scanf(“%s %d”,s,&k)!=EOF) { if(strcmp(s,“0”)==0&&k==0) break; int len=strlen(s),i,j,sum; for(i=0;i

篇4：HDOJ 题目4786 Fibonacci Tree（克鲁斯卡尔）

Fibonacci Tree

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2562 Accepted Submission(s): 816

Problem Description Coach Pang is interested in Fibonacci numbers while Uncle Yang wants him to do some research on Spanning Tree. So Coach Pang decides to solve the following problem:

Consider a bidirectional graph G with N vertices and M edges. All edges are painted into either white or black. Can we find a Spanning Tree with some positive Fibonacci number of white edges?

(Fibonacci number is defined as 1, 2, 3, 5, 8, ... )

Input The first line of the input contains an integer T, the number of test cases.

For each test case, the first line contains two integers N(1 <= N <= 105) and M(0 <= M <= 105).

Then M lines follow, each contains three integers u, v (1 <= u,v <= N, u v) and c (0 <= c <= 1), indicating an edge between u and v with a color c (1 for white and 0 for black).

Output For each test case, output a line “Case #x: s”. x is the case number and s is either “Yes” or “No” (without quotes) representing the answer to the problem.

Sample Input

24 41 2 12 3 13 4 11 4 05 61 2 11 3 11 4 11 5 13 5 14 2 1

Sample Output

Case #1: YesCase #2: No

Source Asia Chengdu Regional Contest

Recommend We have carefully selected several similar problems for you: 5193 5192 5191 5190 5189 ac代码

#include#include#includestruct s{ int u,v,w;}edge[100100];int pre[100100],a[100100],n,m;int cmp1(const void *a,const void *b){ return (*(struct s *)a).w-(*(struct s *)b).w;}int cmp2(const void *a,const void *b){ return (*(struct s *)b).w-(*(struct s *)a).w;}void init(int n){ int i; for(i=0;i<=n;i++) pre[i]=i;}void fun(){ int i; a[1]=1;a[2]=2; for(i=3;i<100100;i++) a[i]=a[i-1]+a[i-2];}int find(int x){ if(x==pre[x]) return pre[x]; return pre[x]=find(pre[x]);}int ku(){ init(n); int ans=0,i,j; for(i=0;i1) return -1; return ans;}int main(){ int t,c=0; scanf(“%d”,&t); fun(); while(t--) { //int n,m int i,l,r; scanf(“%d%d”,&n,&m); //init(n); for(i=0;ir) break; if(a[i]<=r&&a[i]>=l) { printf(“Case #%d: Yesn”,++c); flag=1; break; } } if(!flag) printf(“Case #%d: Non”,++c); } }}

篇5：HDOJ 1076 An Easy Task

【题意】：输入两个数，Y和N，输出从Y（如果Y是闰年则包含Y）开始的第N个闰年。

【代码：AC】

#include#include#include#include#includeusing namespace std;int isLeapYear(int year){ if ((year%4 == 0 && year%100 != 0) || (year%400 == 0)) return 1; return 0;}int main{ int N = 0; cin >>N; while (N--) { int year = 0, n = 0, cnt = 0; cin >>year >>n; while (true) {if(isLeapYear(year++)) cnt++;if (cnt == n) break; } cout<< --year<< endl; }}

篇6：HDOJ 4607 Park Visit

Park Visit

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2225 Accepted Submission(s): 982

Problem Description Claire and her little friend, ykwd, are travelling in Shevchenko's Park! The park is beautiful - but large, indeed. N feature spots in the park are connected by exactly (N-1) undirected paths, and Claire is too tired to visit all of them. After consideration, she decides to visit only K spots among them. She takes out a map of the park, and luckily, finds that there're entrances at each feature spot! Claire wants to choose an entrance, and find a way of visit to minimize the distance she has to walk. For convenience, we can assume the length of all paths are 1.

Claire is too tired. Can you help her?

Input An integer T(T≤20) will exist in the first line of input, indicating the number of test cases.

Each test case begins with two integers N and M(1≤N,M≤105), which respectively denotes the number of nodes and queries.

The following (N-1) lines, each with a pair of integers (u,v), describe the tree edges.

The following M lines, each with an integer K(1≤K≤N), describe the queries.

The nodes are labeled from 1 to N.

Output For each query, output the minimum walking distance, one per line.

Sample Input

4 2

3 2

1 2

4 2

Sample Output

Source Multi-University Training Contest 1

#include

using namespace std;

const int maxn=150100;

struct Edge

{

int to,next;

}edge[maxn*2];

int n,Q,Adj[maxn],Size;

int dist[maxn];

bool vis[maxn];

void init()

{

Size=0; memset(Adj,-1,sizeof(Adj));

}

void Add_Edge(int u,int v)

{

edge[Size].to=v;

edge[Size].next=Adj[u];

Adj[u]=Size++;

}

int get_diameter()

{

queue q;

memset(vis,0,sizeof(vis));

memset(dist,0,sizeof(dist));

q.push(1); vis[1]=true;

while(!q.empty())

{

int v,u=q.front(); q.pop();

for(int i=Adj[u];~i;i=edge[i].next)

{

v=edge[i].to;

if(vis[v]) continue;

vis[v]=1;dist[v]=dist[u]+1;

q.push(v);

}

int goal=-1,mark=-1;

for(int i=1;i<=n;i++)

{

if(dist[i]>mark)

{

mark=dist[i];

goal=i;

}

memset(vis,0,sizeof(vis));

memset(dist,0,sizeof(dist));

q.push(goal); vis[goal]=true;

while(!q.empty())

{

int v,u=q.front(); q.pop();

for(int i=Adj[u];~i;i=edge[i].next)

{

v=edge[i].to;

if(vis[v]) continue;

vis[v]=1; dist[v]=dist[u]+1;

q.push(v);

}

goal=-1;

for(int i=1;i<=n;i++) goal=max(goal,dist[i]);

return goal;

}

int main()

{

int T_T;

scanf(“%d”,&T_T);

while(T_T--)

{

scanf(“%d%d”,&n,&Q);

init();

for(int i=0;i<=“” pre=“”>

篇7：HDOJ 题目4372 Count the Buildings（斯特林第一类数）

Count the Buildings

Time Limit: /1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 738 Accepted Submission(s): 246

Problem Description There are N buildings standing in a straight line in the City, numbered from 1 to N. The heights of all the buildings are distinct and between 1 and N. You can see F buildings when you standing in front of the first building and looking forward, and B buildings when you are behind the last building and looking backward. A building can be seen if the building is higher than any building between you and it.

Now, given N, F, B, your task is to figure out how many ways all the buildings can be.

Input First line of the input is a single integer T (T<=100000), indicating there are T test cases followed.

Next T lines, each line consists of three integer N, F, B, (0Output For each case, you should output the number of ways mod 1000000007(1e9+7).

Sample Input

23 2 23 2 1

Sample Output

Source Multi-University Training Contest 8

Recommend zhuyuanchen520 | We have carefully selected several similar problems for you: 4059 1098 1130 1131 1134 ac代码

#include#include#define mod 1000000007__int64 s[][2010],c[2010][2010],n,f,b;void fun{ int i,j; for(i=0;i<2010;i++) { c[i][0]=1; c[i][i]=1; s[i][0]=0; s[i][i]=1; for(j=0;j

篇8：HDOJ题目2454 Degree Sequence of Graph G（判断是否是简单图）

Degree Sequence of Graph G

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1811 Accepted Submission(s): 750

Problem DescriptionWang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life.

The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of Knoigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below.

AccZ?www.2cto.com/kf/ware/vc/“ target=”_blank“ class=”keylink“>vcmRpbmcgdG8gR3JhcGggVGhlb3J5LCB0aGUgbnVtYmVyIG9mIGVkZ2VzIHJlbGF0ZWQgdG8gYSBub2RlIGlzIGRlZmluZWQgYXMgRGVncmVlIG51bWJlciBvZiB0aGlzIG5vZGUuPGJyPgo8YnI+CldhbmcgSGFpeWFuZyBsb29rZWQgYXQgdGhlIGdyYXBoIGFuZCB0aG91Z2h0LCBJZiBhcnJhbmdlZCwgdGhlIERlZ3JlZSBudW1iZXJzIG9mIGFsbCBub2RlcyBvZiBncmFwaCBHIGNhbiBmb3JtIHN1Y2ggYSBzZXF1ZW5jZTogNCwgNCwgMywzLDIsMiwgd2hpY2ggaXMgY2FsbGVkIHRoZSBkZWdyZWUgc2VxdWVuY2Ugb2YgdGhlIGdyYXBoLiBPZiBjb3Vyc2UsIHRoZSBkZWdyZWUgc2VxdWVuY2Ugb2YgYW55IHNpbXBsZSBncmFwaCAoYWNjb3JkaW5nIHRvCiBHcmFwaCBUaGVvcnksIGEgZ3JhcGggd2l0aG91dCBhbnkgcGFyYWxsZWwgZWRnZSBvciByaW5nIGlzIGEgc2ltcGxlIGdyYXBoKSBpcyBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIHNlcXVlbmNlPzxicj4KPGJyPgpXYW5nIEhhaXlhbmcgaXMgYSB0aG91Z2h0ZnVsIHBlcnNvbiBhbmQgdGVuZHMgdG8gdGhpbmsgZGVlcGx5IG92ZXIgYW55IHNjaWVudGlmaWMgcHJvYmxlbSB0aGF0IGdyYWJzIGhpcyBpbnRlcmVzdC4gU28gYXMgdXN1YWwsIGhlIGFsc28gZ2F2ZSB0aGlzIHByb2JsZW0gZnVydGhlciB0aG91Z2h0LCBBcyB3ZSBrbm93LCBhbnkgYSBzaW1wbGUgZ3JhcGggYWx3YXlzIGNvcnJlc3BvbmRzIHdpdGggYSBub24tbmVnYXRpdmUgaW50ZWdlciBzZXF1ZW5jZS4KIEJ1dCB3aGV0aGVyIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgc2VxdWVuY2UgYWx3YXlzIGNvcnJlc3BvbmRzIHdpdGggdGhlIGRlZ3JlZSBzZXF1ZW5jZSBvZiBhIHNpbXBsZSBncmFwaD8gVGhhdCBpcywgaWYgZ2l2ZW4gYSBub24tbmVnYXRpdmUgaW50ZWdlciBzZXF1ZW5jZSwgYXJlIHdlIHN1cmUgdGhhdCB3ZSBjYW4gZHJhdyBhIHNpbXBsZSBncmFwaCBhY2NvcmRpbmcgdG8gaXQuPzxicj4KPGJyPgpMZXQ=”s put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn‘t studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him?

InputThe first line of input contains an integer T, indicates the number of test cases. In each case, there are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence.

OutputFor each case, the answer should be “yes”or “no” indicating this case is “draw-possible” or “non-draw-possible”

Sample Input

26 4 4 3 3 2 24 2 1 1 1

Sample Output

yesno

Source2008 Asia Regional Harbin

Recommendgaojie | We have carefully selected several similar problems for you: 2448 2452 2451 2453 2455 ac代码

#include#include#includeint cmp(const void *a,const void *b){ return *(int *)b-*(int *)a;}int a[10010];int main(){ int t; scanf(“%d”,&t); while(t--) { int n,i,j,sum=0; scanf(“%d”,&n); for(i=0;i=n) break; } if(i