取数游戏
题目描述： 一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意 两个数字不相邻（若一个数字在另外一个数字相邻 8个格子中的一个即认为这两个数字相 邻），求取出数字和最大是多少。
输入
第一行有两个正整数 N 和 M ，表示了数字矩阵为 N行 M 列。（ 1≤N,M≤6）
输出
输出一个整数，代表符合题目要求的最大的数字和。（样例确保数字和在int范围内）
输入复制
3 3
2 8 9
4 6 4
9 10 7
输出复制
27
#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[10][10]={0};
bool b[10][10]={0};
int n,m;
int ma=-1;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
func(1,1,0);
cout<<ma;
return 0;
}
void func(int x,int y,int sum)
{
if(x==n&&y==m)
{
ma=max(ma,sum);
return;
}
int tx=x,ty=y;
y++;
if(y>m)
{
x++;
y=1;
}
if(b[x][y]==0)
{
b[x][y]=1;
b[x+1][y]=1;
b[x-1][y]=1;
b[x][y+1]=1;
b[x][y-1]=1;
b[x-1][y-1]=1;
b[x-1][y+1]=1;
b[x+1][y-1]=1;
b[x+1][y+1]=1;
func(x,y,sum+a[tx][ty]);
b[x][y]=0;
b[x+1][y]=0;
b[x-1][y]=0;
b[x][y+1]=0;
b[x][y-1]=0;
b[x-1][y-1]=0;
b[x-1][y+1]=0;
b[x+1][y-1]=0;
b[x+1][y+1]=0;
}
func(x,y,sum);
}走出迷宫的最少步数2
题目描述 ：当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫 地图，事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点 到出口的最短路。
输入
第一行是两个整数n和m(1<=nm<=100)表示迷宫的行数和列数。接下来n行，每行一个长为m的字符串，表示整 个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点 'T'表示出口。
输出
输出从起点到出口最少需要走的步数
输入复制
3 3
S#T
.#.
...
输出复制
6
#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int n,m;
char a[110][110];
bool b[110][110]={0};
int sx,sy;
int tx,ty;
int mi=9999999;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
sx=i;
sy=j;
}
if(a[i][j]=='T')
{
tx=i;
ty=j;
}
}
}
func(sx,sy,0);
cout<<mi;
return 0;
}
void func(int x,int y,int cnt)
{
if(x==tx&&y==ty)
{
mi=min(mi,cnt);
return;
}
if(x+1<n&&a[x+1][y]!='#'&&b[x+1][y]==0)
{
b[x+1][y]=1;
func(x+1,y,cnt+1);
b[x+1][y]=0;
}
if(x-1>=0&&a[x-1][y]!='#'&&b[x-1][y]==0)
{
b[x-1][y]=1;
func(x-1,y,cnt+1);
b[x-1][y]=0;
}
if(y+1<m&&a[x][y+1]!='#'&&b[x][y+1]==0)
{
b[x][y+1]=1;
func(x,y+1,cnt+1);
b[x][y+1]=0;
}
if(y-1>=0&&a[x][y-1]!='#'&&b[x][y-1]==0)
{
b[x][y-1]=1;
func(x,y-1,cnt+1);
b[x][y-1]=0;
}
}小明学游泳
题目描述：小明想要学游泳。 这天，小明来到了游泳池，发现游泳池可以用N行M列的格子来表示，每个格子的面积都是1，且格子内水深相同。 由于小明刚刚入门，他只能在水深相同的地方游泳。为此，他把整个游泳池看成若干片区域，如果两个格子相邻 （上下左右四个方向）且水深相同，他就认为它们属于同一片区域。 小X想知道最大的一片区域面积是多少，希望你帮帮他。
输入
第一行包含用一个空格隔开的两个整数N,M。（1≤N,M≤100） 接下来N行，每行包含M个 1到9的数字，表示每个格子的水深
输出
第一行包含一个整数，表示最大的一片区域面积。
样例
输入复制
3 3
1 2 4
2 2 4
1 5 2
输出复制
3
#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[110][110]={0};
bool b[110][110]={0};
int n,m;
int ma=-1;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
func(i,j,1);
}
}
cout<<ma;
return 0;
}
void func(int x,int y,int cnt)
{
b[x][y]=1;
if(x+1<n&&a[x+1][y]==a[x][y]&&b[x+1][y]==0)
{
func(x+1,y,cnt+1);
}
if(x-1<n&&a[x-1][y]==a[x][y]&&b[x-1][y]==0)
{
func(x-1,y,cnt+1);
}
if(y+1<n&&a[x][y+1]==a[x][y]&&b[x][y+1]==0)
{
func(x,y+1,cnt+1);
}
if(y-1<n&&a[x][y-1]==a[x][y]&&b[x][y-1]==0)
{
func(x,y-1,cnt+1);
}
ma=max(ma,cnt);
}小明学游泳2
题目描述：暑假快到啦，小明准备趁着这个暑假去学游泳。可是一开始小 X 就遇到了一个难题。 游泳池划分成了一个 n×m 的方格， 这里 n×m 表示 n 行 m 列。 因 为游泳池里的水深浅不一，所以这 n×m 个方格对 于小明的危险系数也会不一样。 而小 X 目前需要从左上角 的方格（1， 1）出发， 游到右下角 的方格（n， m），小明每次只 能从当前方格游到上下 左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。 小 X 很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。 一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。 注意：这条路径不能经过同一个方格两次（小 X 当然不希望去那么危险的地方再游一次）
输入
输入数据第一行有两个用空格隔开的正整数 n 和 m， 表示泳池的行数和列数。 接下来共有 n 行数据，每行有 m 个用空格隔开的大于等于 0 的整数， 表示每个方格 的危险系数
输出
输出仅有一行包含一个整数ans， 表示要求的从左上角的方格（ 1， 1）出发， 游到 右下角的方格（n， m） 的最小的危险系数。
输入复制
4 5
1 7 2 8 2
3 10 1 5 1
2 8 3 7 1
1 2 1 20 1
输出复制
19
#include<bits/stdc++.h>
using namespace std;
void func(int,int,int);
int a[110][110]={0};
bool b[110][110]={0};
int n,m;
int mi=999999;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
func(0,0,0);
cout<<mi;
return 0;
}
void func(int x,int y,int sum)
{
b[x][y]=1;
if(x==n-1&&y==m-1)
{
sum=sum+a[x][y];
mi=min(mi,sum);
b[x][y]=0;
return;
}
if(x+1<=n-1&&b[x+1][y]==0)
{
func(x+1,y,sum+a[x][y]);
}
if(x-1>=0&&b[x-1][y]==0)
{
func(x-1,y,sum+a[x][y]);
}
if(y+1<=m-1&&b[x][y+1]==0)
{
func(x,y+1,sum+a[x][y]);
}
if(y-1>=0&&b[x][y-1]==0)
{
func(x,y-1,sum+a[x][y]);
}
b[x][y]=0;
}
