Discussion Detail - 追梦算法网

paste
123
oyf Acmer LV 10 MOD @ 2023-11-30 16:58:38

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;

int xb,yb;
int mx,my;
bool vis[30][30];
int dx[]={1,-1,2,-2,2,-2,-1,1},dy[]={2,2,1,1,-1,-1,-2,-2};

bool f(int x,int y){
	if(vis[x][y])return false;
	return true;
}
int dfs(int x,int y){
	if(f(x,y)==false)return 0;
	if(x<0||y<0)return 0;
	if((x==1&&y==0)||(x==0&&y==1)){
		return 1;
	}
	int tmp=dfs(x-1,y)+dfs(x,y-1);
	return tmp;
}
int main( ){
	cin>>xb>>yb>>mx>>my;
	vis[mx][my]=1;
	for(int i=0;i<8;i++){
		int xx=mx+dx[i];
		int yy=my+dy[i];
		vis[xx][yy]=true;
	}
	cout<<dfs(xb,yb)<<endl;
	return 0;
}

oyf Acmer LV 10 MOD @ 2023-11-30 17:21:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=41;


int n,m;
char ma[N][N];
int vis[N][N];
struct st{
	int x,y;
	int sum;
};
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

ll bfs(int x,int y){
	queue<st>q;
	q.push({1,1,1});
	while(!q.empty()){
		st t=q.front();
		q.pop();
		if(vis[t.x][t.y]==1)continue;
		vis[t.x][t.y]=1;
		if(t.x==n&&t.y==m){
			return t.sum;
		}
		for(int i=0;i<4;i++){
			int xx=t.x+dx[i];
			int yy=t.y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&ma[xx][yy]!='#'){
				q.push({xx,yy,t.sum+1});
			}
		}
	}
	return -1;
}
int main( ){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>ma[i][j];
	cout<<bfs(1,1)<<endl;
	return 0;
}