DFS 70分求助(WA#4#7#10) 悬赏1 关注
查看原帖
DFS 70分求助(WA#4#7#10) 悬赏1 关注
819362
Wyy_w123楼主2023/7/10 21:29

(不是m和n的问题)

#include <bits/stdc++.h>

using namespace std;

int n , m , t[101][101] , minn = 10000 , ft[101][101];

int ex[8] = {0 , 1 , 0 , -1 , 1 , -1 , 1 , -1};

int ey[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};

bool f[101][101];

void dfs(int k , int x , int y , int p){
	ft[x][y] = k;
	if(k >= minn){
		return;
	}
	if(x == n && y == m){
		minn = k;
		return;
	}
	for(int i = 0; i < 8; i ++){
		if(i != p){
			int xt = x + ex[i] * t[x][y];
			int yt = y + ey[i] * t[x][y];
			if(xt >= 1 && xt <= n && yt >= 1 && yt <= m && !f[xt][yt] && k + 1 < ft[xt][yt]){
				f[xt][yt] = 1;
				dfs(k + 1 , xt , yt , i);
				f[xt][yt] = 0;
			}
		}
	}
}

int main(){
	cin >> m >> n;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			cin >> t[i][j];
			ft[i][j] = 10000;
		}
	} 
	f[1][1] = 1;
	dfs(0 , 1 , 1 , -1);
	if(minn == 10000){
		cout << "NEVER";
	}else{
		cout << minn;
	}
	return 0;
} 
2023/7/10 21:29
加载中...