jiku (时代一校-吴琪磷)

UID: 4402, 注册于 2023-10-22 13:52:34, 最后登录于 2024-8-19 13:01:49, 目前离线.

解决了 30 道题目，RP: 166.2 (No. 969)

个人简介

基础广搜判断能否到达目的地 0

#include<iostream>
#include<queue>
using namespace std;
char mp[105][105];
int fx[]={-1,1,0,0},fy[]={0,0,-1,1},n,bx,by,ex,ey,m;
bool mk[105][105];
struct Node{
	int x,y;
};
bool bfs(){
	queue<Node> q;
	q.push({bx,by});
	while(q.size()){
		Node t=q.front();
		q.pop();
		if(t.x==ex&&t.y==ey){
			return true;
		}
		for(int i=0;i<4;i++){
			int nx=t.x+fx[i];
			int ny=t.y+fy[i];
			if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]==1||mk[nx][ny]){
				continue;
			}
			q.push({nx,ny});
			mk[nx][ny]=1;
		}
	}
	return false;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='g'){
				bx=i;
				by=j;
			}
			if(mp[i][j]=='s'){
				ex=i;
				ey=j;
			}
			if(mp[i][j]=='#'){
				mk[i][j]=1;
			}
		}
	}
	if(bfs()){
		cout<<"Yes";
	} 
	else{
		cout<<"No";
	}
	return 0;
}

#include<iostream>
#include<queue>
using namespace std;
char mp[105][105];
int fx[]={-1,1,0,0},fy[]={0,0,-1,1},n,bx,by,m,sum=0;
bool mk[105][105];
struct Node{
	int x,y;
};
bool bfs(){
	queue<Node> q;
	q.push({bx,by});
	while(q.size()){
		Node t=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int nx=t.x+fx[i];
			int ny=t.y+fy[i];
			if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='0'||mk[nx][ny]==0){//由于一开始将是细胞的单位当为无细胞所以出错 
				continue;
			}
			if(mk[nx][ny]==1){
				q.push({nx,ny});
				mk[nx][ny]=0;
			}
			
		}
	}  
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]!='0'){``
				mk[i][j]=1;
				mp[i][j]='1';
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			bx=i;
			by=j;
			if(mk[i][j]==1){
				sum++;
				mk[bx][by]=0;//将输入起点当作了标记起点 
				bfs();
			}
		}
	}
	cout<<sum;
	return 0;
}

#include<iostream>
#include<queue>
using namespace std;
char mp[1005][1005];
int fx[]={-1,1,0,0},fy[]={0,0,-1,1},n,bx,by,ex,ey,my[1000][1000];
int mk[1000][1000];
struct Node{
	int x,y;
};
bool bfs(){
	queue<Node> q;
	q.push({bx,by});
	while(q.size()){
		Node t=q.front();
		q.pop();
		if(t.x==ex&&t.y==ey){
			return my[ex][ey];
		}
		for(int i=0;i<4;i++){
			
			int nx=t.x+fx[i];
			int ny=t.y+fy[i];
			if(nx<1||nx>n||ny<1||ny>n||mk[nx][ny]){
				continue;
			}
			q.push({nx,ny});
			mk[nx][ny]=1;
			my[nx][ny]=my[t.x][t.y]+1;
		}
	}
	
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mp[i][j];

if(mp[i][j]=='1'){
			mk[i][j]=1;
		}
	}
}
cin>>bx>>by>>ex>>ey;
my[bx][by]=1;
mp[bx][by]=1;
bfs();
cout<<my[ex][ey]-1;
return 0;

} 2

#include<iostream>
#include<queue>
#include<iomanip>
using namespace std;
int n,m,bx,by,mp[1000][1000],my[1000][1000],fx[100]={-2,-2,-1,+1,+2,+2,-1,+1},fy[100]={-1,+1,+2,+2,-1,+1,-2,-2};
struct Node{
	int x,y;
};
int bfs(){
	queue<Node> q;
	q.push({bx,by});
	mp[bx][by]=1;
	while(q.size()){
		Node t=q.front();
		q.pop();
		for(int i=0;i<8;i++){
			int nx=t.x+fx[i];
			int ny=t.y+fy[i];
			if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]){
				continue;
			}
			q.push({nx,ny});
			mp[nx][ny]=1;
			my[nx][ny]=my[t.x][t.y]+1;
		}
	}
}
int main(){
	cin>>n>>m>>bx>>by;
	my[bx][by]=1;
	bfs();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%-5d",my[i][j]-1);
		}
		cout<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,a,b,h[100000],m[100000],c[100000];
int bfs(){
	queue<int> q;
	q.push(a);
	m[a]=1;
	while(q.size()){
		int x=q.front();
		q.pop();
		if(x==b){
			return true;
		}
		int as[3]={0-h[x],h[x]};
		for(int i=0;i<2;i++){
			int po=x+as[i];
			if(po<1||po>n||m[po]==1){
				continue;
			}
			q.push(po);
			m[po]=1;
			c[po]=c[x]+1;
		}
	}
	return false;
}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	if(bfs()){
		cout<<c[b];
	}
	else{
		cout<<-1;
	}
	return 0;
}

#include<iostream>
using namespace std;
int mp[1000][1000],flag=0,fx[10000]={-1,-1,-1,0,0,1,1,1},fy[10000]={-1,0,1,-1,1,-1,0,1},ex,ey,bx,by,n,sum=0;
int m;
char k;
void dfs(int x,int y){
	for(int i=0;i<8;i++){
		int nx=x+fx[i];
		int ny=y+fy[i];
		if(nx<1||ny<1||nx>n||ny>m||mp[nx][ny]){
			continue;
		}
		mp[nx][ny]=1;
		dfs(nx,ny);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>k;
			if(k=='.'){
				mp[i][j]=1;
			}
			if(k=='w'){
				mp[i][j]=0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]==0){
				mp[i][j]=1;
				dfs(i,j);
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
}

#include<iostream>
using namespace std;
int h,mp[1000][1000],fx[10000]={-1,1,0,0},fy[10000]={0,0,1,-1},ex,ey,bx,by,n,sum=0;
int m,mk[1000][1000];
char k;
void dfs(int x,int y){
	if(x==ex&&y==ey){
		sum++;
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+fx[i];
		int ny=y+fy[i];
		if(nx<1||ny<1||nx>n||ny>m||mp[nx][ny]||mk[nx][ny]){
			continue;
		}
		mk[nx][ny]=1;
		dfs(nx,ny);
		mk[nx][ny]=0;
	}
}
int main(){
	int s,s1;
	cin>>n>>m>>h;
	cin>>bx>>by>>ex>>ey;
	for(int i=1;i<=h;i++){
		cin>>s>>s1;
		mp[s][s1]=1;
		mk[s][s1]=1;
	}
	mk[bx][by]=1;
	dfs(bx,by);
	cout<<sum;
	return 0;
}

#include<iostream>
using namespace std;
int h,mp[1000][1000],fx[10000]={0,-1,0,1},fy[10000]={-1,0,1,0},ex,ey,bx,by,n,sum=0;
int m,mk[1000][1000];
char k;
int s=1;
struct node{
	int a,b;
}jkl[100000];
void dfs(int x,int y){
	jkl[s].a=x;
	jkl[s].b=y;
	if(x==ex&&y==ey){
		sum=1;
		for(int i=1;i<s;i++){
			cout<<"("<<jkl[i].a<<","<<jkl[i].b<<")"<<"->";
		}
		cout<<"("<<jkl[s].a<<","<<jkl[s].b<<")";
		cout<<endl;
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+fx[i];
		int ny=y+fy[i];
		if(nx<1||ny<1||nx>n||ny>m||mp[nx][ny]||mk[nx][ny]){
			continue;
		}
		mk[nx][ny]=1;
		s++;	
		dfs(nx,ny);
		jkl[s].a=0;
		jkl[s].b=0;
		s--;
		mk[nx][ny]=0;
		
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			if(mp[i][j]==1){
				mp[i][j]=0;
			}
			else if(mp[i][j]==0){
				mp[i][j]=1;
			}
		}
	}
	cin>>bx>>by>>ex>>ey;
	mp[bx][by]=1;
	dfs(bx,by);
	if(sum==0){
		cout<<-1;
	}
	return 0;
}

#include using namespace std; struct node{ int x,y; }a[10000]; int p[1000000],py=0,sum=0; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].x; cin>>a[i].y; if(a[i].x>=90&&a[i].y<=140&&a[i].y>=60&&a[i].y<=90){ p[i]=1; } } for(int i=1;i<=n+1;i++){ if(p[i]==1){ sum++; } else{ if(sum>py){ py=sum; } sum=0;

}
}
cout<<py;

} #include<bits/stdc++.h> using namespace std; long long ma=-1,n,a[1000000],b[1000000]; int main(){ cin>>n; cin>>a[1]; b[1]=1; ma=1; for(int i=2;i<=n;i++){ cin>>a[i]; for(int j=i-1;j>=1;j--){ if(a[j]<a[i]){ b[i]=max(b[j]+1,b[i]); } } if(b[i]==0){ b[i]=1; } ma=max(ma,b[i]); } cout<<ma; return 0; }

通过的题目
P1

P2

P3

P106

P108

P111

P112

P373
P380

P560

P722

P898

P1000

T143

T189

T94
P2375

P2376

P2387

P2424

P2427

Y18

Y19

Y21
Y22

Y23

Y24

Y25

Y26

Y27
最近活动

月赛语法: 7
初窥门径: 5
循环结构: 4
顺序结构: 3
驾轻就熟: 3
一本通编程启蒙: 3
略有小成: 2
模拟: 2
GESP三级: 2
月赛算法: 2
while循环: 1
融会贯通: 1
BFS: 1
二分答案: 1
动态规划: 1
NOIP2004提高组: 1
DFS: 1
计数排序: 1
进制转换: 1
数组: 1

jiku (时代一校-吴琪磷)

个人简介

通过的题目

最近活动

题目标签

状态

开发

支持

jiku (时代一校-吴琪磷)

个人简介

通过的题目

最近活动

题目标签

状态

开发

支持

还没有账户？

登录