搜索题目类型各题总结-acm.doc

一个让人感觉很复杂的BFS（但是并不很复杂）
问题 D: BFS_连连看游戏
时间限制: 2 Sec 内存限制: 5 MB
提交: 12 解决: 3
[提交][状态][讨论版]
题目描述
大 家都玩过连连看吧！今天我们玩一个类似的游戏。在一个由10*10个小方格组成的矩形里有n(n<=10)对字符(它们是大写字符中的前n个)。矩 形里有些位置是可以从上面走过，有些则不能。能走过的位置用'.'标识，不能的用'#'标识。如果2个相同字符是连通的(从一个字符能走到另一个字符，注 意走的时候只能向上、下、左、右走。某个位置是有其他字符时，这个位置是不能走的)，那么这对字符能够进行配对。如果将这对字符配对，这对字符将从这个矩 形里消除，也就是说这2个字符所在的位置对于其他字符而言变成能走动了。
现在的问题是：请你决定这些字符的配对顺序(只有能配对才能进行配对)，使得n对字符最后都配对成功。
输入
先给出一个正整数t(t<=10)，表示有t组测试数据。
每组测试数据有10行组成，每行有10个字符。这些字符只能是'.'，'#'，或者是大写字符中的前n个。每组测试数据中不超过10对字符。

输出
如果能够使每组测试数据中的n对字符配对成功，输出配对的顺序。如果有多种配对成功的顺序，输出字典序最小的那组。
否则输出"My God!"。

样例输入
2
ABF.
CE........
D.........
..........
..........
..........
..........
.........D
........EC
.......FBA
ABF.......
CE........
D.........
..........
..........
.........#
........#D
.........#
........EC
.......FBA

样例输出
DCABEF
My God!
参考了下老师的代码 其实我一直的思路也都是这样的 而且还动手写了 但是都是写到一半的时候放弃了 因为心里畏惧 害怕超时
还害怕复杂 以后做一个题目的时候要是有一定的把握就不要畏惧 不要婆婆妈妈的 大大方方的把代码敲出来 干掉它
#include
#include
#include
using namespace std;
int step[4][2]={-1,0,1,0,0,-1,0,1};
char map[11][11];
int used[11][11];
char ans[20];
struct haha
{
int x;
int y;
int step;
friend bool operator <(struct haha a,struct haha b)
{
return a.step>b.step;
}
}q,temp;
int BFS(int x,int y)
{
int x1,y1,i;
priority_queueque;
memset(used,0,sizeof(used));
q.x=x;q.y=y;q.step=0;
used[x][y]=1;
que.push(q);
while(!que.empty())
{
temp=que.top();
que.pop();
for(i=0;i<4;i++)
{
x1=temp.x+step[i][0];
y1=temp.y+step[i][1];
if(x1>=0&&x1<10&&y1>=0&&y1<10used[x1][y1]&&(map[x1][y1]=='.'||map[x1][y1]==map[x][y]))
{
if(map[x1][y1]==map[x][y])
{
map[x1][y1]='.'; map[x][y]='.';return 1;
}
q.x=x1;
q.y=y1;
q.step=temp.step+1;
que.push(q);
used[x1][y1]=1;
}
}
}
return 0;
}
int main()
{
int cas,k;
while(scanf("%d",&cas)!=EOF)
{
while(cas--)
{

int i,j,end=0,end2,flag=0,cnt=0;
for(i=0;i<10;i++)
scanf("%s",map[i]);
while(!end)
{
for(k='A';k<='M'&&!end;k++)/*借鉴老师的方法感觉比较好 一开始就是怕处理太麻烦不敢下手其实只要试着去做的时候才会发现其实没那么复杂*/
{
end2=0;
for(i=0;i<10&&!end2;i++)
for(j=0;j<10&&!end2;j++)//这个终止方法好漂亮啊 省去了一堆break 以前的方法太笨了
{
if(map[i][j]==k)
{
if(BFS(i,j)) {ans[cnt++]=k;end=end2=1;}
else end2=1;
}
}
}
if(end==0) break;
end=0;
}
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(map[i][j]!='.'&&map[i][j]!='#')
{flag=1;break}
}
if(flag) printf("My God!\n");
else
{
for(i=0;iWar
Accepted : 43
Time Limit : 1000 MS

Description
战争即和平，自由即奴役，无知即力量。
——乔治.奥威尔

历史书上说，自从统治者Big Brother去 世以后，大洋国就陷入了无休止的内战中，随时都可能有新的武装势力出现，随时都可能有战争发生。奇怪的是，每次战争都是在当前国内战斗力最强大的两股势力 间进行，我们可以把每股武装势力的战斗力量化成一个值，每次战争都是在当前战斗力值最高的两股势力间进行。如果有多支势力战斗力值相同，则名字字典序大的 在前（见下面第二组样例）。一场战争结束后，战斗力稍弱的那方被消灭，另一方也元气大伤，战斗力减弱为两支武装的战斗力之差。如果发生战争的两方战斗力相 同，则他们会同归于尽。

历史书上详细记录了该段时期的事件，记录分为两种格式：

1) New name value 其中name和value是变量，表示一个名字叫做name，战斗力为value的新势力出现
2) Fight 表示在当前最强的两股势力间发生了战争

现在请你根据书上记录，计算出每场战争以后分别导致哪支（或哪两支）势力被消灭。

输入

输入的第一行包含一个整数T (T ≤ 15)，表示共有T组数据。接下来每组数据的第一行是一个整数N (N ≤ 50000)，表示有N条记录。接下来N行，每行表示一条记录，记录的格式如上所述。输入保证每股势力的名字都不相同，势力的名字仅包含小写字母，长度不超过20。战斗力值为不超过10000的正整数。保证当战争发生时至少有两支势力存在。

输出

对每组数据，输出一行“Case X:”作为开头，此处X为从1开始的编号。注意首字母C为大写，在“Case”和编号X之间有一个空格，在编号X后面有一个冒号。然后对每条Fight记录输出一行，表示被消灭的势力的名字。如果是两支势力同归于尽，则这两个名字都应该输出，字典序大的在前，两个名字之间用一个空格隔开。

样例输入

2

5

New obrien 100

New winston 199

Fight

New julia 99

Fight

4

New miniluv 100

New minipax 100

New minitrue 100

Fight

样例输出

Case 1:

obrien

winston julia

Case 2:

minitrue minipax
"开启时代杯"湘潭市第二届大学生程序设计大赛 (Internet)
#include
#include
#include
using namespace std;
struct haha
{
char s[50];
int val;
bool operator <(const haha &a) const //第一次去尝试 二个判断 以前也没有见过
{
if(val!=a.val) return val0)
return false;
}

}
}q,temp1,temp2;
int main()
{
int i,j,cas;
scanf("%d",&cas);
for(i=1;i<=cas;i++)
{
int n,val;
printf("Case %d:\n",i);
priority_queueduilie;//
char s[30];
scanf("%d",&n);//
while(n--)
{
scanf("%s",s);
if(s[0]'N')
{
scanf("%s %d",q.s,&q.val);
duilie.push(q);
}
else
{
temp1=duilie.top();
duilie.pop();
temp2=duilie.top();
duilie.pop();
if(temp1.val>temp2.val)
{
printf("%s\n",temp2.s);
temp1.val-=temp2.val;
duilie.push(temp1);
}
else
if(temp1.valme Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 628 Accepted Submission(s): 173
Problem Description
Princess claire_ was jailed in a maze by Grand Demon Monster(GDM) teoy.
Out of anger, little Prince ykwd decides to break into the maze to rescue his lovely Princess.
The maze can be described as a matrix of r rows and c columns, with grids, such as 'Y', 'C', '*', '#' and 'P', in it. Every grid is connected with its up, down, left and right grids.
There is only one 'Y' which means the initial position when Prince ykwd breaks into the maze.
There is only one 'C' which means the position where Princess claire_ is jailed.
There may be many '*'s in the maze, representing the corresponding grid can be passed through with a cost of certain amount of money, as GDM teoy has set a toll station.
The grid represented by '#' means that you can not pass it.
It is said that as GDM teoy likes to pee and shit everywhere, this grid is unfortunately damaged by his ugly behavior.
'P' means it is a transmission port and there may be some in the maze. These ports( if exist) are connected with each other and Prince ykwd can jump from one of them to another.

They say that there used to be some toll stations, but they exploded(surely they didn't exist any more) because of GDM teoy's savage act(pee and shit!), thus some wormholes turned into existence and you know the following things. Remember, Prince ykwd has his mysterious power that he can choose his way among the wormholes, even he can choose to ignore the wormholes.
Although Prince ykwd deeply loves Princess claire_, he is so mean that he doesn't want to spend too much of his money in the maze. Then he turns up to you, the Great Worker who loves moving bricks, for help and he hopes you can calculate the minimum money he needs to take his princess back.

Input
Multiple cases.(No more than fifty.)
The 1st line contains 3 integers, r, c and cost. 'r', 'c' and 'cost' is as described above.(0 < r * c <= 5000 and money is in the range of (0, 10000] )
Then an r * c character matrix with 'P' no more than 10% of the number of all grids and we promise there will be no toll stations where the prince and princess exist.

Output
One line with an integer, representing the minimum cost. If Prince ykwd cannot rescue his princess whatever he does, then output "Damn teoy!".(See the sample for details.)

SampleInput
1 3 3
Y*C
1 3 2
Y#C
1 5 2
YP#PC
SampleOutput
3
Damn teoy!

0

题意： Y开始点 C 终止点 P 传送门 与所有传送门连同 # 墙 *能走的地方 但是要钱 只有*要钱
输入 行数 列数 以及钱
问花的 最少的钱是多少
#include
#include
#include
#includeeue>
using namespace std;
int hang,lie,val,cnt;
char map[5100][5100];
struct haha
{
int x;
int y;
int val;
friend bool operator<(struct haha a,struct haha b)
{
return a.val>b.val;
}
}q,temp;
struct p
{
int x;
int y;
}a[5000+10];
int step[4][2]={1,0,-1,0,0,1,0,-1},s_x,s_ye_x,e_y;//把坐标存成了字符型 艾 一天全是低级错误 脑子不清醒
int BFS()
{
int i,j,xx,yy,ans=999999999;
priority_queueque;
q.x=s_x;
q.y=s_y;///////// 已开始这里写成了e_y 想打自己啊
q.val=0;
que.push(q);
map[s_x][s_y]='#';
while(!que.empty())
{
temp=que.top();
que.pop();
for(i=0;i<4;i++)
{
xx=temp.x+step[i][0];
yy=temp.y+step[i][1];
if(xx>=0&&xx=0&&yytemp.val) ans=temp.val;continue;
}
if(map[xx][yy]=='*')
{
map[xx][yy]='#';
q.x=xx;
q.y=yy;
q.val=temp.val+val;//////这里忘记加temp.val MLE了
que.push(q);
continue;
}
if(map[xx][yy]=='P')
{
for(j=0;j q.y=a[j].y;
q.val=temp.val;
que.push(q);
map[q.x][q.y]='#';
}
}
}
}
}

}
return ans;
}
int main()
{
int i,j,ans;
while(scanf("%d %d %d",&hang,&lie,&val)!=EOF)
{
cnt=0;
for(i=0;i
scanf("%s",map[i]);
for(j=0;jturn 0;
}

BFS之打印路径 虐死我得一个题 hdu1026
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6305 Accepted Submission(s): 1882
Special Judge

Problem Description
The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules:

1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).
2.The array is marked with some characters and numbers. We define them like this:
. : The place where Ignatius can walk on.
X : The place is a trap, Ignatius should not walk on it.
n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.

Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.
Input
The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.
Output
For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds) and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX.
5 6
.XX.1.
..X.2.
2...X.
...XX.
XXXXX1
5 6
.XX...
..XX1.

2...X.
...XX.
XXXXX.
Sample Output
It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH
题意：给个二维数组，'.'可以走，'X'不可走，'1-9'代表在此消耗的时间
输出记录从(0,0)到(n-1,m-1)的耗时最小值

#include
#include
using namespace std;
int m,n;
char a[105][105];
int d[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
struct haha
{
int x1;
int y1;
int ti;
friend bool operator < (haha a, haha b)
{
return a.ti > b.ti; //重载小于号使得小的先出队列
}
}q,temp;
int flag[105][105];
struct xixi
{
int x2;
int y2;
}pre[105][105];

void BFS()
{
int i,x,y,time,x0,y0,xi,yi,j,tm;

q.x1=n-1;q.y1=m-1;q.ti=0;
if(a[n-1][m-1]>=48&&a[n-1][m-1]<=57)
q.ti=a[n-1][m-1]-'0';

priority_queueduilie;//这个要放进来 每次都要进行从新分配一个队列 不然的话 就会造成上一次的数据无法清空
duilie.push(q);
while(!duilie.empty())
{
temp=duilie.top();
duilie.pop();
if(temp.x1==0&&temp.y1==0)
{
printf ("It takes %d seconds to reach the target position, let me sh