526互联

DFS

发布时间 2023-11-10 21:14:03作者: W_K_KAI

Oil Deposits

这道题的原题链接Online Judge

自行翻译 == ==

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

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m;
int d[8][2] = { 1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1 }; // 方向数组，表示八个方向
char a[N][N]; // 存储地图的字符数组
int ans; // 记录油田数量

void dfs(int x, int y) { // 深度优先搜索函数
    a[x][y] = '*'; // 将当前位置标记为已访问
    for (int i = 0; i < 8; i++) { // 枚举八个方向
        int nx = x + d[i][0]; // 计算下一个位置的横坐标
        int ny = y + d[i][1]; // 计算下一个位置的纵坐标
        if (nx <= 0 || ny <= 0 || nx > n || ny > m || a[nx][ny] == '*') { // 判断下一个位置是否越界或已访问
            continue; // 如果越界或已访问，则继续枚举下一个方向
        }
        dfs(nx, ny); // 否则继续搜索下一个位置
    }
    return; // 返回
}

int main()
{
    while (cin >> n >> m && (n || m)) { // 多组数据
        ans = 0; // 每组数据初始化油田数量为0
        for (int i = 1; i <= n; i++)
            cin >> a[i]; // 读入地图
        for(int i=1;i<=n;i++)
            for (int j = 1; j <= m; j++) { // 枚举每个位置
                if (a[i][j] == '@'){ // 如果当前位置是油田
                    ans++; // 油田数量加1
                    dfs(i, j); // 开始搜索
                }
            }
        cout << ans << endl; // 输出油田数量
    }
    return 0;
}

滑雪

Time Limit: 1000MS Memory Limit: 65536

Description

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output

25

Source

SHTSC 2002

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
int r,c,ans;
int a[110][110],b[110][110];
int nex[4][2]={1,0,0,1,-1,0,0,-1};
int dfs(int x,int y)
{
	if(b[x][y]!=0)
		return b[x][y];
	for(int i=0;i<4;i++)
	{
		int nx=x+nex[i][0];
		int ny=y+nex[i][1];
		if(nx>=0&&nx<r&&ny>=0&&ny<c&&a[nx][ny]<a[x][y])
		{
			b[x][y]=max(dfs(nx,ny)+1,b[x][y]);//符合条件就递归+1
		}
	}
	return b[x][y];//这一组的长度
}
int main()
{
	cin>>r>>c;
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
		{
			ans=max(ans,dfs(i,j));//找长度最长的一组
		}
	}
	cout<<ans+1<<endl;//开始就是第一个单位长度故+1
	return 0;
}

迷宫（二）

蒜头君在你的帮助下终于逃出了迷宫，但是蒜头君并没有沉浸于喜悦之中，而是很快的又陷入了思考，从这个迷宫逃出的最少步数是多少呢?
输入格式
第一行输入两个整数 \(n\) 和 \(m\) ，表示这是一个 \(n \times m\) 的迷宫。
接下来的输入一个 \(n\) 行 \(m\) 列的迷宫。其中 ' \(\mathrm{S}\) ' 表示蒜头君的位置， ' \(*\) ' 表示墙，蒜头君无法通过，' ' ' 表示路，蒜头君可以通过 '.' 移动， ' \(T\) ' 表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置一上，下，左，右）。

输出格式
输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出 -1 。
数据范围

1≤n,m≤10 。

样例输入1

3  4
s**.
..*.
***T

样例输出 1

-1

样例输入2

3  4
s**.
....
***T

样例输出2

5

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int ans=10000;
char c[21][21];
int flag=0,a,b,e[21][21];
int nex[4][2]={0,1,1,0,-1,0,0,-1};
void dfs(int x,int y,int w)//w是步数
{
	if(w>=ans)
		return ;
	if(c[x][y]=='T')
	{
		flag=1;
		ans=min(ans,w);//走到目的地，寻找走的路最小的
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+nex[i][0];
		int ny=y+nex[i][1];//开始行走
		if(nx<0||ny<0||ny>=b||nx>=a||e[nx][ny]==1||c[nx][ny]=='*')
			continue;//不满足条件
		e[nx][ny]=1;//标记
		dfs(nx,ny,w+1);//步数+1递归
		e[nx][ny]=0;//清零回溯，路走到头了
	}
	return ;
}
int main()
{
	int i,x,y,j;
	cin>>a>>b;
	for(i=0;i<a;i++)
	{
		cin>>c[i];
		for(j=0;j<b;j++)
		{
			if(c[i][j]=='S')//记录 初始位置
			{
				x=i;
				y=j;
			}
		}
	}
	dfs(x,y,0);//从初始位置开始,w为0
	if(flag)
		cout<<ans<<endl;
	else 
		cout<<-1<<endl;
	return 0;
}

马的遍历

洛谷 - P1443

Description
有一个 \(n \times m\) 的棋盘，在某个点 \((x, y)\) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

Input
输入只有一行四个整数，分别为 \(n, m, x, y\) 。

Output
一个 \(n \times m\) 的矩阵，代表马到达某个点最少要走几步 (不能到达则输出 -1 )。

Input

3 3 1 1

Output

0    3    2    
3    -1   1    
2    1    4

数据规模与约定
对于全部的测试点，保证 \(1 \leq x \leq n \leq 400 ， 1 \leq y \leq m \leq\) 400 。

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int N=410;
int nex[][2]={1,2,2,1,-1,2,2,-1,-1,-2,-2,-1,-2,1,1,-2};
int a[N][N];
int m,n,xx,yy;
struct node
{
	int x,y,s;
};
int main()
{
	cin>>n>>m>>xx>>yy;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=-1;
		}
	}
	queue<node >q;
	a[xx][yy]=0;
	node r;
	r.x=xx,r.y=yy,r.s=0;
	q.push(r);
	while(!q.empty())
	{
		node e;
		e=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int nx=e.x+nex[i][0];
			int ny=e.y+nex[i][1];
			if(nx>0&&nx<=n&&ny>0&&ny<=m&&a[nx][ny]==-1)
			{
				node w;
				w.x=nx,w.y=ny,w.s=e.s+1;
				q.push(w);
				a[nx][ny]=w.s;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			/*if(j<n)
				cout<<a[i][j]<<" ";
			else 
				cout<<a[i][j];*/
			printf("%-5d",a[i][j]);
		}
		cout<<endl;
	}
	return 0;
}