國慶期間,省城HZ剛剛舉行了一場盛大的集體婚禮,為了使婚禮進(jìn)行的豐富一些,司儀臨時(shí)想出了有一個(gè)有意思的節(jié)目,叫做"考新郎",具體的操作是這樣的:
首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭隨機(jī)坐成一排;
然后,讓各位新郎尋找自己的新娘.每人只準(zhǔn)找一個(gè),并且不允許多人找一個(gè).
最后,揭開蓋頭,如果找錯(cuò)了對象就要當(dāng)眾跪搓衣板...
看來做新郎也不是容易的事情...
假設(shè)一共有N對新婚夫婦,其中有M個(gè)新郎找錯(cuò)了新娘,求發(fā)生這種情況一共有多少種可能.
Input
輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)C,表示測試實(shí)例的個(gè)數(shù)辈双，然后是C行數(shù)據(jù)，每行包含兩個(gè)整數(shù)N和M(1<M<=N<=20)柜砾。
Output
對于每個(gè)測試實(shí)例湃望，請輸出一共有多少種發(fā)生這種情況的可能，每個(gè)實(shí)例的輸出占一行痰驱。
Sample Input
2
2 2
3 2
Sample Output
1
3
如果有一個(gè)人選錯(cuò)证芭，那就至少還有另一個(gè)人選錯(cuò)；
從N個(gè)新郎担映，挑M個(gè)錯(cuò)排废士，那么也就是說有 N-M 個(gè) 新郎選對了新娘。
#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個(gè)方向進(jìn)行遍歷蝇完，所以創(chuàng)建兩個(gè)數(shù)組x官硝，y進(jìn)行坐標(biāo)的獲得。
BFS里面用二維數(shù)組進(jìn)行遍歷
廣度優(yōu)先搜索短蜕，
滿足條件并且是油田且未遍歷過的氢架，就進(jìn)入隊(duì)列，并標(biāo)記走過
不滿足條件的話朋魔，則head++岖研，直到head>tail
若標(biāo)記過，直接對油田標(biāo)記走過警检，并返回孙援。
用一個(gè)visited數(shù)組來標(biāo)記走過的油田。
#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;
}
