dfs回溯,35pts,其余全wa
查看原帖
dfs回溯,35pts,其余全wa
729338
xihegudiiakioi楼主2024/3/6 18:00
#include <bits/stdc++.h>
using namespace std;
int n,m,a1,b1,a2,b2;
int r[20][3];
int b[17][17];
int fx[5] = {0,0,-1,0,1};
int fy[5] = {0,-1,0,1,0};
int c = false;
void print(int k){//打印函数
	c = true;
	for(int i = 1;i < k;i++){
		cout << '(' << r[i][1] << ',' << r[i][2] <<')' << "->";
	}
	cout << '(' << r[k][1] << ',' << r[k][2] <<')' << endl;
}
void search(int k){//dfs
	int tx,ty;
	for(int i = 1;i <= 4;i++){
		tx = r[k - 1][1] + fx[i];
		ty = r[k - 1][2] + fy[i];
		if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && b[tx][ty] == false){
			r[k][1] = tx;
			r[k][2] = ty;
			b[tx][ty] = true;
			if(tx == a2 && ty == b2){
				print(k);
			}else{
				search(k + 1);
			}
			b[tx][ty] = false;//回溯
		}
	}
}
int main(){
	cin >> n >> m;
	int a;
	for(int i = 1;i <= n;i++){//输入bool数组
		for(int j = 1;j <= m;j++){
			cin >> a;
			if(a == 1){
				b[i][j] = false;
			}else{
				b[i][j] = true;
			}
		}
	}
	cin >> a1 >> b1 >> a2 >> b2;
	b[1][1] = true;
	r[1][1] = a1;
	r[1][2] = b1; 
	search(2);
	if(c == false){
		cout << -1;
	}
  
	return 0;
}
2024/3/6 18:00
加载中...