样例全过,WA测试点一,求助
查看原帖
样例全过,WA测试点一,求助
1221613
wangzc2012楼主2024/6/25 22:23

样例全过,WA测试点一,求助

#include<bits/stdc++.h>
using namespace std;
int m,n,a[15][15],mm=INT_MIN;
bool b[15][15];
long long sum;
int step=INT_MAX;
short int dx[4]={0,-1,0,1};
short int dy[4]={1,0,-1,0};
void dfs(int x,int y,int f,long long ans){
	if (ans+ans>sum) return;
	if (ans+ans==sum){
		step=min(f,step);
		cout<<step;
		exit(0);
	}
	for (int i=0;i<=3;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if (b[tx][ty]==0 and tx<n and ty<m and tx>=0 and ty>=0){
			b[tx][ty]=1;
			dfs(tx,ty,f+1,ans+a[tx][ty]);
			b[tx][ty]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			cin>>a[i][j];
			sum+=a[i][j];
			mm=max(mm,a[i][j]);
		}
	}
	if (mm+mm==sum){
		if (a[0][0]==mm) cout<<1;
		else cout<<m*n-1;
		return 0;
	}
	if (mm>sum/2){
		cout<<0;
		return 0;
	}
	dfs(0,0,1,a[0][0]);
    cout<<0;
	return 0;
}

2024/6/25 22:23
加载中...