前言：
作為一個小白，隻能通過學習宇巨的代碼逐漸提高，是以在這記下來，以後多來看看，學學思路
DFS和BFS都是圖的周遊的兩種形式。
DFS的特點是不具有BFS中按層次順序周遊的特性，是以DFS不具有最優性。DFS是以常用來求解有沒有的問題。DFS所得到的解不一定是最優解。當題目中出現問題是否有解等字眼時，常用DFS來求解。
BFS的特點是按照層次順序周遊，是以，BFS可以用來求解最優解，當題目中出現最短路徑，最少的時間等字眼時，常用BFS來求解。
BFS:
1.迷宮問題（輸出最短字典序列）
下圖給出了一個迷宮的平面圖，其中标記為 1 的為障礙，标記為 0 的為可 以通行的地方。迷宮的入口為左上角，出口為右下角，在迷宮中，隻能從一個位置走到這 個它的上、下、左、右四個方向之一。
010000 000100 001001 110000
請找出一種通過迷宮的方式，
其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案。例如這個例子的輸出: DRRURRDDDR
請注意在字典序中D<L<R<U。
思路：
若用的DFS，程式運作了近 1 小時也得不出答案，最後還會爆棧，這麼大的資料量早該想到的，換用 BFS，因為 BFS 得到的解總是最優解，即步數最少的解，那麼我們在周遊的時候按照字典序從小到大的順序進行四個方向周遊進行了
solve方法是bfs，用到了queue隊列，其中用到了r[][]很重要，記錄了每一步的方向
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100,MAXM=100;
const int f[4]={1,0,0,-1};
const int g[4]={0,-1,1,0};
const char* s="DLRU";
char a[MAXN][MAXM];
int r[MAXN][MAXM];
typedef pair<int,int> P;
int N,M;
void printf(int x,int y)
{
if(x!=1||y!=1){
int t=r[x][y];
printf(x-f[t],y-g[t]);
cout<<s[t];
}
}
void solve(){
queue<P> q;
q.push(P(1,1));
a[1][1]='1';
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=0;i<4;i++){
int nx=x+f[i];
int ny=y+g[i];
if(a[nx][ny]=='0'){
a[nx][ny]='1';
q.push(P(nx,ny));
r[nx][ny]=i;
}
}
}
printf(N,M);
}
int main() {
//cin >> N >> M;
N = 4, M = 6;
memset(a, '1', sizeof(a));
for (int i = 1; i <= N; ++i)
scanf("%s", &a[i][1])/*, a[i][N + 1] = '1'*/;
solve();
return 0;
}
const char* s=“DLRU”;
加星号
2.森林遊記（bfs)
暑假來了，綠紋龍很高興。于是飄飄乎就來到了森林一日遊。可是他卻看到了很不和諧的一幕，一群獵人在森林裡圍捕小動物。森林可以看做是一個10*10的方格，如下圖所示，1表示獵人，0表示小動物。
已知獵人保持不動，而小動物可以往上下左右任意方向逃脫（當然不能撞上獵人）。小動物可以逃出森林。但上圖背景色被标紅的那部分小動物将永遠無法逃脫獵人的魔爪。
Input 一個10*10的矩陣，描述森林中獵人和小動物分布的情況。保證每個點要麼為獵人，要麼為小動物。
Output 一個整數，表示不能逃脫獵人魔爪的小動物數量。
思路：
先bfs整個矩陣，把能走出去的vis标記為1，然後最後統計vis為0的即可
bfs過程中 因為不能出去的那些都是被1圍住的，像圍棋，是以bfs是走不到裡面的
code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
const ll mod = 1e9+7;
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void out(ll x) {
int stackk[40];
if (x < 0) {
putchar('-');
x = -x;
}
if (!x) {
putchar('0');
return;
}
int top = 0;
while (x) stackk[++top] = x % 10, x /= 10;
while (top) putchar(stackk[top--] + '0');
}
int a[12][12],n=10,vis[12][12];
int dx[4]= {1,0,-1,0};
int dy[4]= {0,1,0,-1};
void bfs() {
queue<PII>q;
q.push({0,0});
vis[0][0] = 1;
while(q.size()) {
PII fr = q.front();
q.pop();
int x = fr.first;
int y = fr.second;
for(int i=0 ; i<4 ; i++) {
int x1 = x+dx[i];
int y1 = y+dy[i];
if(vis[x1][y1]) continue;
if(a[x1][y1]) continue;
if(x1<0||x1>n+1||y1<0||y1>n+1) continue;
vis[x1][y1] =1;
q.push({x1,y1});
}
}
}
int main() {
int s=0;
// rep(i,0,n) rep(j,0,n) a[i][j] =0;
rep(i,1,n) rep(j,1,n) a[i][j] = read();
bfs();
int ans=0;
rep(i,1,n) rep(j,1,n) if(a[i][j]==0&&vis[i][j]==0) ans++;
out(ans);
return 0;
}
/*
*/
3.馬的周遊
題目描述
有一個n*m的棋盤(1<n,m<=400)，在某個點上有一個馬,要求你計算出馬到達棋盤上任意一個點最少要走幾步
輸入格式
一行四個資料，棋盤的大小和馬的坐标
輸出格式
一個n*m的矩陣，代表馬到達某個點最少要走幾步（左對齊，寬5格，不能到達則輸出-1）
輸入輸出樣例
輸入
3 3 1 1
輸出
0 3 2
3 -1 1
2 1 4
code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};//8個方向
queue<pair<int,int> > q;
int f[500][500];//存步數
bool vis[500][500];
int main(){
int n,m;
int x,y;
cin>>n>>m>>x>>y;
memset(f,-1,sizeof(f));
memset(vis,false,sizeof(vis));
f[x][y]=0;
vis[x][y]=true;
q.push(make_pair(x,y));
while(!q.empty())
{
int xx=q.front().first;
int yy=q.front().second;
q.pop();
for(int i=0;i<8;i++)
{
int u=xx+dx[i],v=yy+dy[i];
if(u<1||u>n||v<1||v>m||vis[u][v])continue;//出界或走過就不走
vis[u][v]=true;q.push(make_pair(u,v));f[u][v]=f[xx][yy]+1;
}
}
for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++)printf("%-5d",f[i][j]);printf("\n");}//注意場寬！！
return 0;
}
4.奇怪的電梯
題目描述呵呵，有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第ii層樓(1≤i≤N)上有一個數字K i。電梯隻有四個按鈕：開，關，上，下。上下的層數等于目前樓層上的那個數字。當然，如果不能滿足要求，相應的按鈕就會失靈。例如：3, 3 ,1
,253,3,1,2,5代表了K_i在1樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那麼，從A樓到B樓至少要按幾次按鈕呢？
輸入格式 共二行。
第一行為33個用空格隔開的正整數，表示N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。
第二行為NN個用空格隔開的非負整數，表示K_iK i
輸出格式
一行，即最少按鍵次數,若無法到達，則輸出-1−1。
輸入輸出樣例
輸入
5 1 5
3 3 1 2 5
輸出
3
code(dfs):
#include<cstdio>
#include<iostream>
using namespace std;
int n,a,b,ans=0x7ffffff;
int to[205];
bool vis[205];
void dfs(int now,int sum)//now表示目前搜到的樓層,sum表示按鈕次數
{
if(now==b) ans=min(ans,sum);
if(sum>ans) return;
vis[now]=1;
//不越界就搜
if(now+to[now]<=n&&!vis[now+to[now]]) dfs(now+to[now],sum+1);
if(now-to[now]>=1&&!vis[now-to[now]]) dfs(now-to[now],sum+1);
vis[now]=0;//回溯
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++) scanf("%d",&to[i]);
vis[a]=1;
dfs(a,0);
if(ans!=0x7ffffff) printf("%d",ans);
else printf("-1");
return 0;
}
code(bfs):
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a,b,to[205];
bool vis[205];
struct node{int id,step;}x;//id表示樓層号，step表示按鈕次數
queue<node> q;
int main(){
cin>>n>>a>>b;
for(int i=1;i<=n;i++) cin>>to[i];
q.push((node){a,0});
while(q.size())
{
x=q.front();
q.pop();
if(x.id==b)
{
cout<<x.step<<endl;
return 0;
}
if(x.id+to[x.id]>=1&&!vis[x.id+to[x.id]])
{
q.push((node){x.id+to[x.id],x.step+1});
vis[x.id+to[x.id]]=1;
}
if(x.id-to[x.id]>=1&&!vis[x.id-to[x.id]])
{
q.push((node){x.id-to[x.id],x.step+1});
vis[x.id-to[x.id]]=1;
}
}
printf("-1");
return 0;
}
DFS
1.着色問題
給定一個具有n個頂點的圖。要給圖上的每個頂點染色、并且要使相鄰的頂點顔色不同。問是否能最多用2種顔色進行染色？題目保證沒有重邊和自環。
思路：
judge函數是判斷以pos為起點，有無存在一條邊使二維數組等于1，且相鄰的這個點顔色不重複
code:
#include<iostream>
using namespace std;
const int MAX=105; //定義最大的頂點數
int n,m,num,ans; //分别代表點數、邊數、可用顔色數和最終的答案
int map[MAX][MAX]; //對于小規模的數量可以直接使用鄰接矩陣（也可以用向量優化空間）
int color[MAX]; //color[i]=x表示第i個點塗上代号為x的顔色
bool judge(int pos,int col) //檢測在pos位上塗顔色代号為col的方案是否可行
{
for(int i=1;i<=n;i++)
if(map[pos][i] && color[i]==col) return false;
return true;
}
void dfs(int pos)
{
if(pos>n){
ans++;
return;
}
for(int i=1;i<=num;i++){
if(judge(pos,i)) //如果可以在pos位上塗上顔色i
{
color[pos]=i; //那麼就給pos位塗上顔色i
dfs(pos+1);
color[pos]=0; //回退時必須把剛才點的着色去掉，否則有可能會影響下次的dfs
}
}
}
int main()
{
int x,y;
cin>>n>>m>>num;
for(int i=0;i<m;i++)
{
cin>>x>>y;
map[x][y]=map[y][x]=1;
}
dfs(1);
cout<<ans<<endl;
return 0;
}
2.分考場
n個人參加某項特殊考試。
為了公平，要求任何兩個認識的人不能分在同一個考場。
求是少需要分幾個考場才能滿足條件。
輸入格式
第一行，一個整數n(1<n<100)，表示參加考試的人數。 第二行，一個整數m，表示接下來有m行資料
以下m行每行的格式為：兩個整數a，b，用空格分開 (1<=a,b<=n) 表示第a個人與第b個人認識。
輸出格式
一行一個整數，表示最少分幾個考場。
思路：
先對所有教室進行周遊，每次周遊一個教室的時候，周遊此時這個人和教室裡每個人的關系是否為1，如果出現認識，那就周遊下一個教室。如果教室全周遊完，就再開一間教室，記得下面為回溯做準備，設定pop_back
dfs結束條件即是安排的學生數量大于原本的人數，這一層return結束，開始回溯
code：
#include<iostream>
#include<vector>
using namespace std;
const int MAX=105;
bool map[MAX][MAX]; //map[x][y]表示x和y認識
int n,m;
int ans=MAX; //最開始必須給ans指派一個最大值（為最多的人數即可）
vector<int> classroom[MAX]; //二維向量classroom[i]=x表示
void dfs(int order,int roomNum) //order表示某個學生的序号，roomNum表示目前教室的數量
{
if(roomNum>=ans) return; //當現在安排的教室數量已經大于了最小的教室數量的話放棄搜尋并回退
if(order>n){ //安排的學生數量已經大于所有的學生，就表示已經安排完了所有的學生
ans=roomNum;
return;
}
for(int i=1;classroom[i].size();i++) //周遊所有教室
{
int j,len=classroom[i].size();
for(j=0;j<len;j++) //檢測目前教室是否存在一個人與将要被安排的學生認識
if(map[order][classroom[i][j]]) break;
if(j==len) //說明目前教室中沒有人與目前order的學生認識
{
classroom[i].push_back(order); //在目前教室插入此學生
dfs(order+1,roomNum); //繼續安排下一個
classroom[i].pop_back(); //回退時需要把這個學生從目前教室清除掉
}
}
classroom[roomNum+1].push_back(order); //開一間新教室給目前學生
dfs(order+1,roomNum+1); //繼續安排下一個
classroom[roomNum+1].pop_back(); //回退後需要把這個學生從目前教室清除掉
}
int main()
{
int x,y;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>x>>y;
map[x][y]=map[y][x]=1;
}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
3.走方格
【問題描述】
在平面上有一些二維的點陣。
這些點的編号就像二維數組的編号一樣，從上到下依次為第 1 至第 n 行，
從左到右依次為第 1 至第 m 列，每一個點可以用行号和列号來表示。
現在有個人站在第 1 行第 1 列，要走到第 n 行第 m 列。隻能向右或者向下
走。
注意，如果行号和列數都是偶數，不能走入這一格中。
問有多少種方案。
【輸入格式】
輸入一行包含兩個整數 n, m。
【輸出格式】
輸出一個整數，表示答案。
【樣例輸入】
3 4
【樣例輸出】
2
【樣例輸入】
6 6
【樣例輸出】
【評測用例規模與約定】
對于所有評測用例，1 ≤ n ≤ 30, 1 ≤ m ≤ 30。
*/
code:
#include<Stdio.h>
int n,m;
int cns=0;
int dfs(int a,int b)
{
if(a%2==0&&b%2==0) return 0;
if(a==n&&b==m) cns++;
if(a+1<=n) dfs(a+1,b);
if(b+1<=m) dfs(a,b+1);
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1,1);
printf("%d",cns);
return 0;
}
4.分兩半
把一個6*6正方形分成兩半，一共多少種方案
思路：
沿着線進行dfs，而不是對格子
code:
#include<bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool vis[10][10];
int res=0;
void dfs(int x,int y){
if(x==0||y==0||x==6||y==6){
res++;
return;
}
for(int i=1;i<=4;i++)
{
int tempx=x+dir[i][0];
int tempy=y+dir[i][1];
if(!vis[tempx][tempy])
{
vis[tempx][tempy]=1;
vis[6-tempx][6-tempy]=1;
dfs(tempx,tempy);
vis[tempx][tempy] = 0;
vis[6-tempx][6 - tempy] = 0;
}
}
}
int main()
{
vis[3][3] = 1;
DFS(3,3);
cout << ans/4 <<endl;
return 0;
}
5.小天狼星的通路
經過數月的準備，小天狼星，一個被誣陷的殺人犯，準備闖入霍格沃茨見見他的侄子。霍格沃茨的地圖呈一顆樹狀分布。每個房間由若幹跳過道通向其他房間。由于小天狼星想盡快找到哈利：
0.他會從房間0開始找
1.他總是會選擇離自己最近的房間找
2.如果沒找到，則繼續選最近的房間深入
3.如果已沒有房間可走，則傳回到上一個房間，繼續選擇（往回走也算時間哦）。
4.當然，除了往回走,小天狼星是不會去一個房間兩次的。
Input 第1行，n房間個數，p哈利所在的房間。(p≤n<100)
第2∼n行，每行3個整數s,t,l。從房間s到房間t的時間l。(s≠t, 0≤s<t<n, 0<l≤10000)
Output 輸出找到哈利的時間(開始時間為0)。
Samples
Input Copy
5 2
0 1 1
0 2 2
1 3 3
1 4 4
Output
18
思路：
這個最近的房間不是根據數字大小，而是到達相連房間時間最少的那一個。找到下一個點後，标記此點搜尋過，然後判斷到達目标點了嗎，沒有的話dfs找到的這個點，如果此點後無路徑，回溯至上一層，同時時間也要加上回來的時間
ps:不是所有的題都套用模闆 标記走過為1 回溯變為0 像塗色問題确實是這樣，因為不恢複原本 都無法找到下一個不一樣的塗色方案
但像此題，比如到達4點，标記來過，回溯的時候加上了回來的時間，但是不用取消标記，因為下次通路不會再來他了，就不用再錯一次了
code:
#include<cstdio>
#include<string>
#define MAXN 100+10
#define oo 99999999
int n,p,ans=0,map[MAXN][MAXN];
bool h[MAXN];
void dfs(int i)
{
int k,min,j;
while(true)
{
k=0;min=oo;
for(j=1;j<=n;j++)
if(!h[j] && map[i][j]>0 && min>map[i][j])
{min=map[i][j];k=j;}
if(min==oo) return;
h[k]=true;
ans+=map[i][k];//從 i 到 k
if(k==p){printf("%d",ans);exit(0);}
dfs(k);
ans+=map[i][k];//無路可走時從 k 回到 i
}
}
int main()
{
scanf("%d%d",&n,&p);
int i,s,t,l;
for(i=1;i<=n-1;i++)
{
scanf("%d%d%d",&s,&t,&l);
map[s][t]=l;map[t][s]=l;
}
h[0]=true;
dfs(0);
printf("%d",ans);
return 0;
}
6.活蹦亂跳的香穗子
香穗子在田野上調蘑菇!她跳啊跳,發現自己很無聊,于是她想了一個有趣的事情,每個格子最多隻能經過1次,且每個格子都有其價值
跳的規則是這樣的,香穗子可以向上下左右四個方向跳到相鄰的格子,并且她隻能往價值更高(這裡是嚴格的大于)的格子跳.
香穗子可以從任意的格子出發,在任意的格子結束, 那麼她最多能跳幾次?
Input
第一行n,m, 表示田野的長和寬
接下來n行,每行m個數,表示該格的價值
Output
一個數,表示最多跳得格數
Samples
Input Copy
2 2
2 5
-1 3
Output
2
思路：
需要從每個點出發，來判斷最大值是多少，是以循環dfs，每次dfs的時候做好vis标記是否走過，并且回溯取消标記。每次循環dfs前先恢複vis數組原始值
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 700;
const ll mod = 1e9+7;
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void out(ll x) {
int stackk[40];
if (x < 0) {
putchar('-');
x = -x;
}
if (!x) {
putchar('0');
return;
}
int top = 0;
while (x) stackk[++top] = x % 10, x /= 10;
while (top) putchar(stackk[top--] + '0');
}
ll qpow(ll a,ll b) {
ll ans=1;
while(b) {
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
//int n,m,a,b;
//vector<int>v[666];
ll n,m,a[121][122];
ll dx[4] = {1,-1,0,0};
ll dy[4]= {0,0,1,-1};
ll vis[121][121],ans,step[121][121],vi[121][102];
void dfs(ll x,ll y,ll val) {
ans = max(ans,val);
for(int i=0 ; i<4 ; i++) {
int x1 = x+dx[i];
int y1 = y+dy[i];
if(x1<1||x1>n||y1<1||y1>m) continue;
if(a[x1][y1]<=a[x][y]) continue;
if(vi[x1][y1]) continue;
vi[x1][y1] =1;
dfs(x1,y1,val+1);
vi[x1][y1] =0;
}
}
int main() {
/*
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1 ; i<=m ; i++) {
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
*/
n=read(),m=read();
rep(i,1,n) rep(j,1,m) a[i][j]=read();
for(int i=1 ; i<=n ; i++) {
for(int j=1 ; j<=m ; j++) {
// if(vis[i][j]) continue;
mst(vi,0);
dfs(i,j,0);
}
}
out(ans);
return 0;
}
/*
7.P1036 [NOIP2002 普及組] 選數
題目描述：
已知 n 個整數 從n個整數中任選k個整數相加，可分别得到一系列的和。例如當n=4,k=3 4個整數分别為3,7,12,19時，可得全部的組合與它們的和為：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
現在，要求你計算出和為素數共有多少種。
例如上例，隻有一種的和為素數：3+7+19=29
思路：
例如 3 7 12 19進行深搜即可
先是第1個循環 i=0 i<4 隻走了第一層 也就是sum加入了3
然後第2個循環 i=1 i<4 隻走了第一層 也就是sum加入了7
然後第3個循環 i=2 i<4 隻走了第一層 也就是sum加入了12
然後判讀這三個數是否是素數 判斷完後開始回溯
先回溯了第三個循環 開始從i=3執行 便是 3 7 19
再回溯了第二個循環 開始從i=2執行 便是 3 12
然後i=3 便是3 12 19
再回溯第一個循環
code：
#include <iostream>
#include <cstdio>
using namespace std;
bool isprime(int a){//判斷素數
/*0和1特判真的沒啥用對這題
吐槽：題中n的資料範圍很奇怪，
n還有可能=1.....那k<n......
*/
for(int i = 2;i * i <= a; i++)//不想用sqrt，還要頭檔案
if(a % i == 0)//如果整除
return false;//扔回false
//程式都到這裡的話就說明此為素數
//否則就被扔回了
return true;//扔回true
}
int n,k;
int a[25];
long long ans;
void dfs(int m, int sum, int startx){//最重要的遞歸
//m代表現在選擇了多少個數
//sum表示目前的和
//startx表示升序排列，以免算重
if(m == k){//如果選完了的話
if(isprime(sum))//如果和是素數
ans++;//ans加一
return ;
}
for(int i = startx; i < n; i++)
dfs(m + 1, sum + a[i], i + 1);//遞歸
//步數要加一，和也要加
//升序起始值要變成i+1,以免算重
return ;//這一個步驟下，所有的都枚舉完了
//直接傳回去
}
int main(){
scanf("%d%d",&n,&k);//輸入
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);//循環讀入
dfs(0,0,0);//調用函數
printf("%d\n",ans);//輸出答案
return 0;//結束程式
}
8.P2089 烤雞
豬豬 Hanke 特别喜歡吃烤雞（本是同畜牲，相煎何太急！）Hanke 吃雞很特别，為什麼特别呢？因為他有 10 種配料（芥末、孜然等），每種配料可以放 1 到 3 克，任意烤雞的美味程度為所有配料品質之和。
現在， Hanke 想要知道，如果給你一個美味程度 n ，請輸出這 10 種配料的所有搭配方案。
輸入
1
輸出
1
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
思路：
1.可以十層for循環暴力跑，這題不逾時
2.dfs搜尋 關鍵在于怎麼儲存這十個數，可以開個數組儲存，回溯的時候記得取消
code：
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans1,ans2[10001][11],sum,a[11];
void trys(int t,int m)//t代表目前的嘗試的調料。m代表目前美味程度
{
if (t>10)
{
if (m==n) //如果美味程度與豬豬的要求相等
{
ans1++;//統計方案總數
for (int i=1;i<=10;i++)
ans2[ans1][i]=a[i];//存入答案的數組
}
return ;
}
for (int i=1;i<=3;i++)
{
if (m+i>n) break;//如果超過了要求，那麼後面的就可以直接忽略
a[t]=i;//儲存答案
trys(t+1,m+i);//檢視下一種調料
a[t]=0;//狀态恢複
}
}
int main()
{
cin>>n;
trys(1,0);//從第一種調料開始嘗試，美味程度為0
cout<<ans1<<endl;
for (int i=1;i<=ans1;i++)
{
for (int j=1;j<=10;j++)
cout<<ans2[i][j]<<" ";
cout<<endl;
}//輸出結果
return 0;
}
9.敢死隊（經典思路）
code:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int sol_sup[100005];
bool vis[100005];
int n;
int ans;
bool check(int idx)
{
if(vis[sol_sup[idx]]) return false;
return true;
}
void choose(int sum,int need,int idx)
{
if(sum==need)
{
ans++;
return;
}
for(int i=idx+1;i<=n;i++){
if(check(i))
{
vis[i]=1;
choose(sum+1,need,i);
vis[i]=0;
}
}
}
int main()
{
//輸入
cin >> n;
sol_sup[1] = 1;
for (int i = 2; i <= n; i++) cin >> sol_sup[i];
//選1~n個成員
for (int i = 1; i <= n; i++)
{
memset(vis, 0, sizeof(vis));
choose(0, i, 0);
}
cout << ans;
return 0;
}
10.數獨題
code：
#include<iostream>
using namespace std;
int map[10][10];
int range(int n)
{
if (n >= 1 && n <= 3) return 1;
else if (n >= 4 && n <= 6) return 4;
else return 7;
}
bool check(int x, int y, int n)
{
//檢查行列
for (int i = 1; i <= 9; i++)
{
if (map[x][i] == n || map[i][y] == n) return false;
}
//檢查九宮格
int r = range(x);
int c = range(y);
for (int i = r; i <= r + 2; i++)
{
for (int j = c; j <= c + 2; j++)
{
if (map[i][j] == n) return false;
}
}
return true;
}
void dfs(int x, int y)
{
//完成填數，輸出
if (y > 9)
{
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
cout << map[i][j];
}
cout << endl;
}
exit(0);
}
if (map[x][y] == 0)
{
for (int i = 1; i <= 9; i++)
{
if (check(x, y, i))
{
map[x][y] = i;
dfs((x + 1) % 10, y + (x + 1) / 10);
map[x][y] = 0;
}
}
}
else dfs((x + 1) % 10, y + (x + 1) / 10);
}
int main()
{
//輸入
for (int i = 1; i <= 9; i++)
{
string s;
cin >> s;
for (int j = 0; j < 9; j++)
{
if (s[j] != '0') map[i][j + 1] = s[j] - '0';
}
}
dfs(1, 1);
return 0;
}