30pts求调
查看原帖
30pts求调
799536
Cold_Eyes_bystander楼主2024/7/11 11:08
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char ch[1001][1001];
int b[1001][1001],c[1001][1001];
void dfs(int x,int y,int cnt,int sum)
{
	if(b[x][y]<cnt)
	{
		return;
	}
	if(c[x][y]<=sum&&b[x][y]==cnt)
	{
		return;	
	}	
	b[x][y]=cnt,c[x][y]=sum;
	if(x!=n&&y!=m&&ch[x][y]=='\\')
	{
		if(ch[x+1][y+1]=='\\')
		{
			dfs(x+1,y+1,cnt,sum+1);
		}
		else
		{
			ch[x+1][y+1]='\\';
			dfs(x+1,y+1,cnt+1,sum+1);
			ch[x+1][y+1]='/';
		}
	}
	if(x!=1&&y!=m&&ch[x][y]=='/')
	{
		if(ch[x-1][y+1]=='/')
		{
			dfs(x-1,y+1,cnt,sum+1);
		}
		else
		{
			ch[x-1][y+1]='/';
			dfs(x-1,y+1,cnt+1,sum+1);
			ch[x-1][y+1]='\\';
		}
	}
	if(x!=1&&y!=1&&ch[x][y]=='\\')
	{
		if(ch[x-1][y-1]=='\\')
		{
			dfs(x-1,y-1,cnt,sum+1);
		}
		else
		{
			ch[x-1][y-1]='\\';
			dfs(x-1,y-1,cnt+1,sum+1);
			ch[x-1][y-1]='/';
		}
	}
	if(x!=n&&y!=1&&ch[x][y]=='/')
	{
		if(ch[x+1][y-1]=='/')
		{
			dfs(x+1,y-1,cnt,sum+1);
		}
		else
		{
			ch[x+1][y-1]='/';
			dfs(x+1,y-1,cnt+1,sum+1);
			ch[x+1][y-1]='\\';
		}
	}
	if(y!=m)
	{
		if(ch[x][y+1]!=ch[x][y])
		{
			dfs(x,y+1,cnt,sum+1);
		}
		else
		{
			dfs(x,y+1,cnt+1,sum+1);
		}
	}
	if(y!=1)
	{
		if(ch[x][y-1]!=ch[x][y])
		{
			dfs(x,y-1,cnt,sum+1);
		}
		else
		{
			dfs(x,y-1,cnt+1,sum+1);
		}
	}
	if(x!=n)
	{
		if(ch[x+1][y]!=ch[x][y])
		{
			dfs(x+1,y,cnt,sum+1);
		}
		else
		{
			dfs(x+1,y,cnt+1,sum+1);
		}
	}
	if(x!=1)
	{
		if(ch[x-1][y]!=ch[x][y])
		{
			dfs(x-1,y,cnt,sum+1);
		}
		else
		{
			dfs(x-1,y,cnt+1,sum+1);
		}
	}
} 
signed main()
{
    cin>>n>>m;
    for(int i=0;i<=1000;i++)
    {
    	for(int j=0;j<=1000;j++)
    	{
    		b[i][j]=1e18;
    		c[i][j]=1e18;
		}
	}
    if(n%2!=m%2)
    {
        cout<<"NO SOLUTION";
        return 0;
    }
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>ch[i][j];
		}
	}
	cout<<1;
    return 0;
}
2024/7/11 11:08
加载中...