问两道题..

常规
1

1.90分
洛谷P4328

#include<bits/stdc++.h>
using namespace std;
int vis[51][51],v[51][51],z[51][51],ex,ey,n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
char a[51][51];
struct node
{
	int x,y,ans;
};
queue<node>q;
void bfs1()
{
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		for(int i=0;i<4;++i)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&v[nx][ny]==99999&&a[nx][ny]!='X'&&a[nx][ny]!='D')
			{
				v[nx][ny]=min(v[nx][ny],now.ans+1);
				q.push({nx,ny,now.ans+1});
			}
		}
	}
}
void bfs2(int x,int y)
{
	q.push({x,y,0});
	while(!q.empty())
	{	
		node now=q.front();
		q.pop();
		if(z[now.x][now.y])
		{
			cout<<now.ans;
			return;
		}
		for(int i=0;i<4;++i)
		{
			int nx=now.x+dx[i];
			int ny=now.y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&(a[nx][ny]=='.'||a[nx][ny]=='D')&&v[nx][ny]>now.ans)
			{
				vis[nx][ny]=1;
				q.push({nx,ny,now.ans+1});
			}
		}
	}
	cout<<"KAKTUS";
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j) v[i][j]=99999;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	{
		cin>>a[i][j];
		if(a[i][j]=='*')
		{
			v[i][j]=0;
			q.push({i,j,0});
		}
		if(a[i][j]=='S')
		{
			ex=i;
			ey=j;
		}
		if(a[i][j]=='D') z[i][j]=1;
	}
	bfs1();
	vis[ex][ey]=1;
	bfs2(ex,ey);
	return 0;
}

2.80分
洛谷P10108

#include<bits/stdc++.h>
using namespace std;
int dp[20005],a[101],w[20005],m,n,v,t;
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=0;i<m;++i) cin>>w[i];
	for(int i=1;i<=m*2;++i)
	{
		v=INT_MIN;
		for(int j=1;j<=n;++j)
		if(i>=a[j]&&i-a[j]<m) v=max(v,dp[i-a[j]]+w[i-a[j]]);
		dp[i]=v;
	}
	for(int i=m;i<=m*2;++i) t=max(t,dp[i]+w[i]);
	cout<<t;
	return 0;
}
5 个赞
2

第二题已解决

5 个赞
3

我没洛谷号，题目发一个呗

2 个赞
4

image
image788×825 30.9 KB

2 个赞
5

这是第一题的

2 个赞
6

这是洪水填充问题

2 个赞
7

也就是领地问题

2 个赞
8

时间限制: 1000ms

空间限制: 262144kB

题目描述

时间：1s 空间：256M

题目描述：

给你一个地图，你位于地图中的某一个点，只要你能达到的位置都可以成为你的领地。问你有多少位置可以成为你的领地。你只能走上下左右四个方向。

输入格式：

输入一行，包含两个整数n,mn,m.

接下来mm行每行nn个字符。

#表示障碍物，不能经过

@表示你的位置

其他都是空地

输出格式：

输出一个整数。

样例输入：

6 9 …#. …# … … … … … #@…# .#…#.

样例输出：

45

约定：

1 <=n ,m<=20 1 <=n ,m<=20

#include<bits/stdc++.h>
using namespace std;
char mp[25][25];
bool vis[25][25];
int n,m,sx,sy,cnt=0;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
void dfs(int x,int y);
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]=='@'){
				sx=i;sy=j;
			}
		}
	}
	
	vis[sx][sy]=true;
	dfs(sx,sy);
	cout<<cnt;
	return 0;
}
void dfs(int x,int y){
	cnt++;
	for(int i=0;i<4;i++)
	{
		int xi=x+dx[i];
		int yi=y+dy[i];
		if(0<xi&&xi<=m&&0<yi&&yi<=n&&mp[xi][yi]!='#'&&vis[xi][yi]==false){
			vis[xi][yi]=true;
			dfs(xi,yi);
		}
	}	 
}
3 个赞
9

我知道呀我问你我哪错了