1.求連通子塊
#表示草地，上下左右連通的草地視為同一塊草地，求一共多少塊草地
#include<stdio.h>
char map[20][20];
bool flag[20][20];
int n,m;
void dfs(int x,int y)
{
if(x < 0 || x >= n || y < 0 || y >= m || flag[x][y] ||map[x][y] == '.')
{
return;
}
flag[x][y] = true;
dfs(x+1,y);
dfs(x,y+1);
dfs(x-1,y);
dfs(x,y-1);
}
int main()
{
int ans = 0;
scanf("%d%d",&n,&m);
for(int i =0;i<n;i++)
{
scanf("%s",map[i]);
}
for(int i =0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[i][j] == '#' && flag[i][j] == false)
{
dfs(i,j);
ans++;
}
}
}
printf("%d",ans);
return 0;
}
2.求最大連通（上下左右連通的*）子塊
#include<stdio.h>
char map[20][20];
bool flag[20][20];
int n,m,cnt;
void dfs(int x,int y)
{
if(x<0||x>=n||y<0||y>=m||flag[x][y]||map[x][y]=='.')
{
return;
}
cnt++;
flag[x][y] = true;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main()
{
int ans = 0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",&map[i]);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[i][j] == '*')
{
cnt = 0;
dfs(i,j);
if(ans<cnt) ans = cnt;
}
}
}
printf("%d",ans);
return 0；
}
3.組合的輸出
題目描述
排列與組合是常用的數學方法，其中組合就是從n個元素中抽出r個元素(不分順序且r < ＝ n)，我們可以簡單地将n個元素了解為自然數1，2，…，n，從中任取r個數。
現要求你不用遞歸的方法輸出所有組合。
例如n ＝ 5 ，r ＝ 3 ，所有組合為：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
輸入
一行兩個自然數n、r ( 1 < n < 21，1 < ＝ r < ＝ n )。
輸出
所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，所有的組合也按字典順序。
#include<iostream>
using namespace std;
int n,r;
int res[25];
bool vis[25];
void dfs(int index)
{
if(index == r+1)
{
for(int i=1;i<=r;i++)
{
printf("%d ",res[i]);
}
printf("\n");
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i]&&i>res[index-1])
{
res[index] = i;
vis[i] = true;
dfs(index+1);
vis[i] = false;
}
}
}
int main()
{
scanf("%d%d",&n,&r);
dfs(1);
return 0;
}
4.組合+判斷素數
題目描述
已知 n 個整數b1,b2,…,bn
以及一個整數 k（k＜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。
輸入
第一行兩個整數：n , k （1<=n<=20，k＜n）
第二行n個整數：x1,x2，…,xn （1<=xi<=5000000）
輸出
一個整數（滿足條件的方案數）。
樣例輸入
4 3
3 7 12 19
樣例輸出
1
#include<iostream>
#include<string.h>
using namespace std;
int n,k,ans,sum;
int num[30];
int sel[30];//select數組裡裝的是所選擇的數的下标，用來比較順序
bool vis[30];
//判斷素數
bool isPrime(int n)
{
if(n<=1) return false;
for(int i=2;i*i<=n;i++)
{
if(n%i==0) return false;
}
return true;
}
void dfs(int index)
{
if(index == k+1)
{
if(isPrime(sum)) ans++;
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i] && i>sel[index-1])
{
sum+=num[i];//維護一個sum
sel[index] = i;//裝的是所選擇的數的下标，用來比較順序
vis[i] = true;
dfs(index+1);
vis[i] = false;
sum-=num[i];//回溯時減去它
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
sel[i]=i;//也可以不寫，第一次選擇數字本來就是按順序的
}
dfs(1);
printf("%d",ans);
return 0;
}
5.走迷宮
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 1216 解決: 403
[送出][狀态][讨論版][命題人:外部導入]
題目描述
有一個n*m格的迷宮(表示有n行、m列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，檔案讀入這n*m個資料和起始點、結束點(起始點和結束點都是用兩個資料來描述的，分别表示這個點的行号和列号)。現在要你程式設計找出所有可行的道路，要求所走的路中沒有重複的點，走時隻能是上下左右四個方向。如果一條路都不可行，則輸出相應資訊(用-l表示無路)。
請統一用 左上右下的順序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)
輸入
第一行是兩個數n，m( 1 < n ， m < 15 )，接下來是m行n列由1和0組成的資料，最後兩行是起始點和結束點。
輸出
所有可行的路徑，描述一個點時用(x，y)的形式，除開始點外，其他的都要用“->”表示方向。
如果沒有一條可行的路則輸出-1。
樣例輸入
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6 樣例輸出
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6) #include<iostream>
#include<string.h>
#include<vector>
#include<utility>
using namespace std;
int m[15][15];
//bool vis[15][15];
bool hasLoad;
int x,y,bx,by,ex,ey;
vector<pair<int, int>> ans;
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
void dfs(int nowx,int nowy)
{
if(nowx == ex && nowy == ey)
{
hasLoad=true;
printf("(%d,%d)",bx,by);
for(int i=0;i<ans.size();i++)
{
printf("->(%d,%d)",ans[i].first,ans[i].second);
}
printf("\n");
return;
}
for(int i=0;i<4;i++)
{
int curx=nowx+dir[i][0];
int cury=nowy+dir[i][1];
if(curx>=1 && curx<=x && cury>=1 && cury<=y && m[curx][cury]==1)
{
m[curx][cury]=0;
ans.push_back(make_pair(curx,cury));
dfs(curx,cury);
m[curx][cury]=1;
ans.pop_back();
}
}
}
int main()
{
while(~scanf("%d%d",&x,&y))
{
memset(m,0,sizeof(m));
hasLoad=false;
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
scanf("%d",&m[i][j]);
}
}
scanf("%d%d%d%d",&bx,&by,&ex,&ey);
//記得将起點标記為不可走。
m[bx][by]=0;
dfs(bx,by);
m[bx][by]=1;//最後換不還原無所謂
if(!hasLoad) printf("-1\n");
}
return 0;
}
![Java資料結構—稀疏數組問題引入二維數組與稀疏數組課後練習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)