今天下午組隊賽，隊伍一共A了5道題，我A了兩道題，一道是水題，還有一道dfs的題目。
Huatuo was a famous doctor. He use identical bottles to carry the medicine. There are different types of medicine. Huatuo put medicines into the bottles and chain these bottles together.
However, there was a critical problem. When Huatuo arrived the patient’s home, he took the chain out of his bag, and he could not recognize which bottle contains which type of medicine, but he remembers the order of the bottles on the chain.
Huatuo has his own solution to resolve this problem. When he need to bring 2 types of medicines, E.g. A and B, he will put A into one bottle and put B into two bottles. Then he will chain the bottles in the order of ′−B−A−B−′. In this way, when he arrived the patient’s home, he knew that the bottle in the middle is medicine A and the bottle on two sides are medicine B.
Now you need to help Huatuo to work out what’s the minimal number of bottles needed if he want to bring N
types of medicine.
Input
The first line of the input gives the number of test cases, T(1≤T≤100). T lines follow. Each line consist of one integer N(1≤N≤100)
, the number of types of the medicine.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y
is the minimal number of bottles Huatuo needed.
Sample Input
1
2
Sample Output
Case #1: 3
水題一枚，意思是讓你幫助華佗分配藥物讓他可以能快速找到藥物。
題目已經給出思路-A-B-A-,接下來就是-A-B-C-B-A-故可知需要的瓶子數爲藥物種類數的二倍減一，屬於一個簡單的遞推。
AC程式碼
#include <stdio.h>
#include<stdlib.h>
#include <string.h>
#include <math.h>
int main()
{
int t,n,i=0;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("Case #%d: %d\n",++i,2*n-1);
}
return 0;
}
Yi Sima was one of the best counselors of Cao Cao. He likes to play a funny game himself. It looks like the modern Sudoku, but smaller.
Actually, Yi Sima was playing it different. First of all, he tried to generate a 4×4 board with every row contains 1 to 4, every column contains 1 to 4. Also he made sure that if we cut the board into four 2×2
pieces, every piece contains 1 to 4.
Then, he removed several numbers from the board and gave it to another guy to recover it. As other counselors are not as smart as Yi Sima, Yi Sima always made sure that the board only has one way to recover.
Actually, you are seeing this because you’ve passed through to the Three-Kingdom Age. You can recover the board to make Yi Sima happy and be promoted. Go and do it!!!
Input
The first line of the input gives the number of test cases, T(1≤T≤100).
T test cases follow. Each test case starts with an empty line followed by 4 lines.
Each line consist of 4 characters. Each character represents the number in the corresponding cell (one of ‘1’, ‘2’, ‘3’, ‘4’). ‘*’ represents that number was removed by Yi Sima.
It’s guaranteed that there will be exactly one way to recover the board.
Output
For each test case, output one line containing Case #x:, where x
is the test case number (starting from 1). Then output 4 lines with 4 characters each. indicate the recovered board.
Sample Input
3
****
2341
4123
3214
*243
*312
*421
*134
*41*
**3*
2*41
4*2*
Sample Output
Case #1:
1432
2341
4123
3214
Case #2:
1243
4312
3421
2134
Case #3:
3412
1234
2341
4123
司馬懿喜歡玩數獨，最後還統一了天下，所以喜歡玩數獨==能統一天下。（開玩笑【笑哭】）
這是一道dfs的題，就像經典問題馬踏棋盤一樣，需要把符合條件的一個一個的試，可以的話就繼續，不行就回溯。
輸出的條件爲你從（1,1）遍歷到了（4,4）。
AC程式碼
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[10];
int f;
int hang[10][10], lie[10][10], m[10][10];
int g(int x, int y, int a)//g函數爲判斷一個點是否符合要求的函數
{
for (int i = 1; i <= 4; i++)//行不重
{
if (m[x][i] == a)
return 0;
}
for (int i = 1; i <= 4; i++)//列不重
{
if (m[i][y] == a)
return 0;
}
if(x>0&&x<3)//左上、左下、右上、右下四個小正方形不重
{
if(y>0&&y<3)
{
if(m[1][1]==a||m[1][2]==a||m[2][1]==a||m[2][2]==a)
return 0;
}
else if(m[1][3]==a||m[1][4]==a||m[2][3]==a||m[2][4]==a)
return 0;
}
else
{
if(y>0&&y<3)
{
if(m[3][1]==a||m[3][2]==a||m[4][1]==a||m[4][2]==a)
return 0;
}
else if(m[3][3]==a||m[3][4]==a||m[4][3]==a||m[4][4]==a)
return 0;
}
return 1;
}
void dfs(int x, int y)//深度優先搜尋
{
if (f)
return;//f==1,逐層退出遞回
else if (y > 4)
{
for (int i = 1; i <= 4; i++)
{
for (int j = 1; j <= 4; j++)
{
printf("%d", m[i][j]);
}
printf("\n");
}
f = 1;
return;
}
else if (x > 4)//x第一次大於4，即第一列遍歷完成
dfs(1, y + 1);
else if (!m[x][y])
{
for (int i = 1; i <= 4; i++)
{
if (!hang[x][i] && !lie[y][i] && g(x, y, i))
{
hang[x][i] = lie[y][i] = 1;
m[x][y] = i;
dfs(x + 1, y);
m[x][y] = 0;
hang[x][i] = lie[y][i] = 0;
}
}
}
else dfs(x + 1, y);
}
int main()
{
int t, i, j, k = 1;
scanf("%d", &t);
while (t--)
{
memset(hang, 0, sizeof(hang));
memset(lie, 0, sizeof(lie));
for (i = 1; i <= 4; i++)
{
scanf("%s", s);
for (j = 1; j <= 4; j++)
{
if (s[j-1] == '*')
{
m[i][j] = 0;//標記該位置有沒有數位
}
else
{
m[i][j] = s[j-1] - '0';
hang[i][m[i][j]] = 1;
lie[j][m[i][j]] = 1;
}
}
}
f = 0;
printf("Case #%d:\n", k++);
dfs(1, 1);
}
return 0;
}
對於dfs的題目還是不夠熟悉，導致該題目浪費了較長的時間，dfs和bfs還需要加強練習。
加油！！！！