Sol

阅读完题意，不难联想到搜索。

因为要求出最右下角的答案，所以我们需要先找出所有答案。

考虑进行搜索，用 $z_{i,j}$ 表示走到 $(i,j)$ 的最小代价。因为每个点最多走不到很多次，穿墙的其实很少，所以时间复杂度 $\mathcal O(nm)$。

Code

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y;
	long long va;
};
long long n,m,a,b;
long long aa[120][120];
long long h[120][120];
pair<long long,long long> vis[120][120];
long long dx[]={1,-1,0,0};
long long dy[]={0,0,1,-1};
void dfs(long long x,long long y){
	h[x][y]=1;
	for(long long i=0;i<4;i++){
		long long tx=x+dx[i];
		long long ty=y+dy[i];
		if(tx>0&&tx<=n&&ty>0&&ty<=m&&h[tx][ty]==0&&aa[tx][ty]==0)dfs(tx,ty);
	}
}
queue<node> q;
long long z[120][120];
long long ans=0x3f3f3f3f3f3f3f3f;
long long xx,yy;
main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>a>>b;
	memset(z,0x3f,sizeof z);
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			cin>>aa[i][j];
		}
	}
    memset(vis,0x3f,sizeof vis);
	dfs(1,1);
	q.push(node{1,1,0});
	vis[1][1]=make_pair(1,0);
	z[1][1]=0;
	while(!q.empty()){
		long long x=q.front().x;
		long long y=q.front().y;
		long long va=q.front().va;
		q.pop();
		for(long long i=0;i<4;i++){
			long long tx=x+dx[i];
			long long ty=y+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&aa[tx][ty]==0&&vis[tx][ty].second>va+a){
				vis[tx][ty].second=va+a;
				q.push(node{tx,ty,va+a});
				z[tx][ty]=min(z[tx][ty],va+a);
			}
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&aa[tx][ty]==1&&aa[tx+dx[i]][ty+dy[i]]==0&&vis[tx+dx[i]][ty+dy[i]].second>va+b){
				tx+=dx[i];
				ty+=dy[i];
				vis[tx][ty].second=va+b;
				q.push(node{tx,ty,va+b});
				z[tx][ty]=min(z[tx][ty],va+b);
			}
		}
	}
	for(int i=n;i>=1;i--){
		for(long long j=m;j>=1;j--){
			if(ans>z[i][j]&&h[i][j]==0){
				ans=z[i][j];
				xx=i;
				yy=j;
			}
		}
	}
	if(ans==0x3f3f3f3f3f3f3f3f){
		cout<<"No";
		return 0;
	}
	cout<<"Yes\n";
	cout<<ans<<" ("<<xx<<","<<yy<<")";
	return 0; 
}

Nothing