[SHOI2002] 滑雪

题目描述

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$（从 $24$ 开始，在 $1$ 结束）。当然 $25$－$24$－$23$－$\ldots$－$3$－$2$－$1$ 更长。事实上，这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

样例 #1

样例输入 #1

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

样例输出 #1

25

提示

对于 $100\%$ 的数据，$1\leq R,C\leq 100$。

找错找了半个小时

#include<cstdio>
#include<iostream>
using namespace std;

int dp[105][105],a[105][105],r,c;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int dfs(int x,int y){
	if(dp[x][y]) return dp[x][y];
	int maxn=0;
	for(int i=0;i<4;i++){
		int xx=dx[i]+x;
		int yy=dy[i]+y;
		if(xx>=0&&yy>=0&&xx<r&&yy<c&&a[x][y]>a[xx][yy]){
			maxn=max(maxn,dfs(xx,yy));
		}
	}
	return dp[x][y]=maxn+1;
}
int main(void){
	cin>>r>>c;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			cin>>a[i][j];
		}
	}
	int count=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			count=max(count,dfs(i,j));
		}
	}
	cout<<count<<endl;
	return 0;
}

引爆炸弹

题目描述

在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。 数据范围：1≤n,m≤1000

输入格式

第一行两个空格隔开的整数 n,m （1≤n,m≤1000）。

第二行至第n+1行有一个 n×m 的地图，其中字符 0 表示该位置没有炸弹，字符 1 表示该位置有炸弹。

输出格式

输出一个整数。表示引爆地图上的所有炸弹引爆，最少需要手动引爆多少个炸弹。

样例输入

5 5
00010
00010
01001
10001
01000

样例输出

2

#include<cstdio>
#include<iostream>
using namespace std;

int h[1005],l[1005],n,m,count=0;
char a[1005][1005];
int dfs(int x,int y){
	a[x][y]=0;
	if(h[x]==0){//找行上没有被引爆的炸弹 
		h[x]=1;//引爆 
		for(int i=0;i<m;i++) if(a[x][i]=='1') dfs(x,i);//顺带把该炸弹所在列全部引爆 
	}
	if(l[y]==0){//找列上没有被引爆的炸弹 
		l[y]=1;//引爆
		for(int i=0;i<n;i++) if(a[i][y]=='1') dfs(i,y);//顺带把该炸弹所在行全部引爆 
	}
}
int main(void){
	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++){
			if(a[i][j]=='1'){//引爆炸弹 
				dfs(i,j);
				count++;//累计被手动引爆的炸弹数量 
			}
		}
	}
	cout<<count<<endl;
	return 0;
}