dfs 6pts求调 AC+WA+TLE+MLE
查看原帖
dfs 6pts求调 AC+WA+TLE+MLE
1161278
happy_lion楼主2025/1/13 18:10
#include<bits/stdc++.h>
using namespace std;
char a[310][310];
int f[310][310];
int c[310][310][2];
int mn = 1e9;
int zx,zy;
int n,m;
void dfs(int x,int y,int s) {
	if (x == zx && y == zy) {
		mn = min(mn,s);
		return ;
	}
    if (f[x][y]) {
        f[x][y] = min(f[x][y],s);
        return ;
    }
	if (x > n || x < 1 || y > m || y < 1) {
		return ;
	}
	if (!(c[x][y][0] != x || c[x][y][1] != y)) {
        f[x][y] = s;
    }
    int yx = x;
	x = c[x][y][0];
	y = c[yx][y][1];
	dfs(x+1,y,s+1);
	dfs(x,y+1,s+1);
	dfs(x-1,y,s+1);
	dfs(x,y-1,s+1);
	f[x][y] = 0;
}
int main() {
	cin >> n >> m;
	int qx,qy;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			cin >> a[i][j];
			if (a[i][j] == '@') {
				qx = i;
				qy = j;
			} else if (a[i][j] == '=') {
				zx = i;
				zy = j;
			}
			if (a[i][j] >= 'A' && a[i][j] <= 'Z' && !c[i][j][0]) {
                bool flag = true;
				for (int ii=1;ii<=n;ii++) {
					for (int jj=1;jj<=m;jj++) {
						if ((ii != i || jj != j) && a[ii][jj] == a[i][j]) {
							c[i][j][0] = ii;
							c[i][j][1] = jj;
							c[ii][jj][0] = i;
							c[ii][jj][1] = j;
                            flag = false;
							break;
						}
					}
				}
                if (flag) {
                    c[i][j][0] = i;
				    c[i][j][1] = j;
                }
			} else {
				c[i][j][0] = i;
				c[i][j][1] = j;
			}
		}
	}
	dfs(qx,qy,0);
	cout << mn;
}
2025/1/13 18:10
加载中...