国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:
image.png
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
最后,揭开盖头,如果找错了对象就要当众跪搓衣板...
看来做新郎也不是容易的事情...
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。
Output
对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
Sample Input
2
2 2
3 2
Sample Output
1
3
如果有一个人选错，那就至少还有另一个人选错；
从N个新郎，挑M个错排，那么也就是说有 N-M 个 新郎选对了新娘。
#include <iostream>
using namespace std;
int main()
{
int c,i,j;
int m,n;
long long sm[21];
long long a[21];
sm[0]=1;
sm[1]=0;
a[0]=1;
a[1]=1;
for(j=2;j<21;j++){
sm[j]=(j-1)*(sm[j-1]+sm[j-2]);
a[j]=j*a[j-1];
}
cin>>c;
for(i=0;i<c;i++){
cin>>n>>m;
cout<<sm[m]*(a[n]/a[m]/a[n-m])<<endl;
}
return 0;
}
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
油田问题：
油田的整体面积可以8个方向进行遍历，所以创建两个数组x，y进行坐标的获得。
BFS里面用二维数组进行遍历
广度优先搜索，
满足条件并且是油田且未遍历过的，就进入队列，并标记走过
不满足条件的话，则head++，直到head>tail
若标记过，直接对油田标记走过，并返回。
用一个visited数组来标记走过的油田。
#include<iostream>
#include<cstring>
using namespace std;
int M, N, total;
char map[110][110];
int visited[110][110];
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0,-1,-1, -1 };
struct queue {
int xx;int yy;
}que[10100];
void find_oil(int x, int y)
{
int x1, y1;
int head, tail;
if (!visited[x][y])
{
total++;//第一次遍历
visited[x][y] = 1;
}
if (visited[x][y] == 1)
{
head = 0, tail = 1;
que[0].xx = x;
que[0].yy = y;
while (tail > head)
{
x = que[head].xx;
y = que[head].yy;
for (int i = 0;i < 8;i++)
{
x1 = x + dx[i];y1 = y + dy[i];
if (x1 >= 1 && x1 <= M && y1 >= 1 && y1 <= N)
if (map[x1][y1] == '@' && !visited[x1][y1])
{
que[tail].xx = x1;
que[tail].yy = y1;
visited[x1][y1] = 1;
tail += 1;
}
}
head++;
}
}
}
void BFS()
{
for (int i = 1;i <= M;i++)
for (int j = 1;j <= N;j++)
if (map[i][j] == '@' && !visited[i][j])
find_oil(i, j);
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> M >> N)
{
cin.get();
if (M <= 0 || N <= 0) break;
total = 0;
memset(map, 0, sizeof(map));
memset(visited, 0, sizeof(visited));
for (int i = 1;i <= M;i++)
for (int j = 1;j <= N;j++)
cin >> map[i][j];
BFS();
cout << total << endl;
}
return 0;
}
网友评论