12分dfs求调
查看原帖
12分dfs求调
730504
lizeyuhello楼主2024/3/3 21:52
#include<bits/stdc++.h>
using namespace std;

int n, m, ans;
int sx, sy, fx, fy;
int doorx, doory;
int d[305][305];
char a[305][305];
bool vis[305][305];
int dx[] = { 0, 1, 0,-1};
int dy[] = { 1, 0,-1, 0};

void door(char c, int x, int y)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] == c && i != x && j != y)
			{
				doorx = i, doory = j;
				return;
			}
		}
	}
	return;
}

void dfs(int x, int y, int step)
{
	if (d[x][y] < step)
		return;
	d[x][y] = step;
	if (a[x][y] == '=')
		return;
	vis[x][y] = 1;
	for (int i = 0, tx, ty; i < 4; i++)
	{
		tx = x + dx[i], ty = y + dy[i];
		if (a[tx][ty] == '#' || vis[tx][ty] || tx < 1 || tx > n || ty < 1 || ty > m)
			continue;
		if (isupper(a[tx][ty]))
			door(a[tx][ty], tx, ty), dfs(doorx, doory, step + 1);
		dfs(tx, ty, step + 1);
	}
	vis[x][y] = 0;
	return;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(d, 0x3f, sizeof(d));
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == '@')
				sx = i, sy = j;
			else if(a[i][j] == '=')
				fx = i, fy = j;
		}
	}
	dfs(sx, sy, 0);
	cout << d[fx][fy];
 	return 0;
}

诶,这什么垃圾代码,又臭又长的……

2024/3/3 21:52
加载中...