这道题还能怎么剪枝啊?
查看原帖
这道题还能怎么剪枝啊?
1050431
DevilsFlame楼主2023/12/6 12:23
#include<bits/stdc++.h>
using namespace std;
int f[2][1000],dx[4]={0,1,-1,0},dy[4]={1,0,0,-1},ans=100001,n,c,m[1001][1001];
char s[100][100];
int bfs(int x,int y,int r){
	int l=r;
	if(x==n&&y==c&&l<ans){
		ans=r;
		f[0][r]=x;
		f[1][r]=y;
		return 1;
	}
	if(r>ans)
		return 2;
	bool q=0;
	for(int i=0;i<=3;i++){
		if((x+dx[i])<=n&&(y+dy[i])<=c&&(x+dx[i])>0&&(y+dy[i])>0&&s[x+dx[i]][y+dy[i]]!='*'&&m[x+dx[i]][y+dy[i]]==1){//判断是否可以走
			m[x+dx[i]][y+dy[i]]=0;//回溯
			if(bfs(x+dx[i],y+dy[i],l+1)==1){
				q=1;
				f[0][r]=x;
				f[1][r]=y;
			}
			m[x+dx[i]][y+dy[i]]=1;//同上
		}
	}
	if(q){
		return 1;
	}
	return 2;
}
int main(){
	int x=1,y=1;
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=c;j++){
			cin>>s[i][j];
			m[i][j]=1;
		}
	}
	if(bfs(x,y,1)==2){
		cout<<-1<<endl;
	}
	else{
		for(int i=1;i<=ans;i++){
			cout<<f[0][i]<<' '<<f[1][i]<<endl;
		}
	}
	return 0;
}
2023/12/6 12:23
加载中...