20分求调 玄关
查看原帖
20分求调 玄关
931492
xiaohuanxiong楼主2024/5/16 21:53
#include<bits/stdc++.h>
using namespace std;
int n,m;
int mx; 
int xa,ya,xb,yb,dis[501][501]={};
char a[501][501];
int check(int p,int q)
{
	if (p<q) return p;
	return q;
}
void dfs(int x,int y,int ans,char s)
{
	
	if (x==xb&&y==yb)
	{
		mx=check(ans,mx);
		return ;
	}
	dis[x][y]=1;
	if (x+1<n&&dis[x+1][y]!=1) 
	{
		if (a[x+1][y]!=s)	ans+=1;
		dfs(x+1,y,ans,a[x+1][y]);
		if (a[x+1][y]!=s)	ans-=1;
	}
	if (y-1>=0&&dis[x][y-1]!=1)
	{
		if (a[x][y-1]!=s)	ans+=1;
		dfs(x,y-1,ans,a[x][y-1]);
		if (a[x][y-1]!=s)	ans-=1;
	} 
	if (x-1>=0&&dis[x-1][y]!=1)
	{
		if (a[x-1][y]!=s)	ans+=1;
		dfs(x-1,y,ans,a[x-1][y]);
		if (a[x-1][y]!=s)	ans-=1;
	} 
	if (y+1<m&&dis[x][y+1]!=1)
	{
		if (a[x][y+1]!=s)	ans+=1;
		dfs(x,y+1,ans,a[x][y+1]);
		if (a[x][y+1]!=s)	ans-=1;
	} 
}
int main()
{
	cin>>n>>m;
	while (n!=0&&m!=0)
	{
		for (int i=0;i<n;i++)
			for (int j=0;j<m;j++)	
				cin>>a[i][j];
		cin>>xa>>ya>>xb>>yb;
		
		mx=10000000;
		memset(dis,0,sizeof(dis));
		dfs(xa,ya,0,a[xa][ya]);
		cout<<mx<<endl;
		cin>>n>>m;
	}
	return 0;
}
2024/5/16 21:53
加载中...