第一题:
Oil Deposits

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 1412 Accepted Submit: 780

--------------------------------------------------------------------------------
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.

Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2

翻译一下,上面的那个矩阵表示的是一块土地,@代表的是油,你的任务是找出土地上有多少快油,比如第一个例子只有一块是:
@ @
@
@ @ 要是翻译的不是很清楚,大家自己用金山,
提交地址:http://acm.zju.edu.cn/show_problem.php?pid=1709

第二
Sorting by Swapping
Time Limit:1000MS Memory Limit:10000K
Total Submit:2753 Accepted:1471

Description
Given a permutation of numbers from 1 to n, we can always get the sequence 1, 2, 3, ..., n by swapping pairs of numbers. For example, if the initial sequence is 2, 3, 5, 4, 1, we can sort them in the following way:

2 3 5 4 1
1 3 5 4 2
1 3 2 4 5
1 2 3 4 5

Here three swaps have been used. The problem is, given a specific permutation, how many swaps we needs to take at least.

Input
The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each case contains two lines. The first line contains the integer n (1 <= n <= 10000), and the second line gives the initial permutation.

Output
For each test case, the output will be only one integer, which is the least number of swaps needed to get the sequence 1, 2, 3, ..., n from the initial permutation.

Sample Input

2
3
1 2 3
5
2 3 5 4 1

Sample Output

0
3

翻译:求选择排序的时候交换的次数.注意排序的元素很特殊,他们是从1开始的连续的自然数序列!!!
提交地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1674
两个题目都不是很难,只要大家多动动脑筋一定都能做出来

[此贴子已经被作者于2007-6-9 9:52:02编辑过]

好久没有来了,沙发都没有占到,
大家注意第一个题目我可能翻译的不是很准确,

[此贴子已经被作者于2007-6-9 21:09:05编辑过]

第一个题目我和leeco的算法一样.都是DFS,时间都是0MS,空间多点400多K.
第二个有点不一样:
#include<stdio.h>
int main()
{
int t,n,a[10005],b[10005],sum,i,j,min,temp;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=i;
sum=0;
for(i=1;i<=n;i++)
{
if(b[i]==i) continue;
else
{
b[a[i]]=b[i];
a[b[i]]=a[i];
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}

下期出题的任务.继续交给leeco

算法没有错.
我没有给你去提交.不过我看你大致是直接模拟选择排序,然后再纪录交换次数.但是在输入10000个数的时候这个O(N^2)的算法不能在1S内算出答案.
你没有注意看我的提示.
排序的数据是有特点的,他们是连续的1,2,3,4,...,N.排好序之后应该是1,2,3,....N,
继续改进一下.