Monsters WA84（3WA1TLE）求条

周善孝 · 2024 年7 月 28 日 08:25

好久以前的错误danm码了，题面：

Danm码：

#include<bits/stdc++.h>
using namespace std;
 long long I=0,J=0,n,m,a[1010][1010],b[1010][1010],d[2][4]={{0,0,1,-1},{1,-1,0,0}},A,B;
 char c[1010][1010];
struct node{
 	long long xx,yy;
}l,pre[1010][1010];
void bfs(long long i,long long j){
	queue<node>q;
	q.push({i,j});
 	while(!q.empty()){
 		l=q.front();
 		q.pop();
 		for(long long ij=0;ij<4;ij++){
 			long long X=l.xx+d[0][ij],Y=l.yy+d[1][ij];
 			if(c[i][j]=='M'){
 				if(X>=1&&Y>=1&&X<=n&&Y<=m&&(c[X][Y]=='.'||c[X][Y]=='A')&&a[X][Y]>a[l.xx][l.yy]+1){
					a[X][Y]=a[l.xx][l.yy]+1;
					q.push({X,Y});
				}
			}else{
				if(X>=1&&Y>=1&&X<=n&&Y<=m&&b[X][Y]==-1&&c[X][Y]=='.'&&b[l.xx][l.yy]+1<a[X][Y]){
 					pre[X][Y]={l.xx,l.yy};
					b[X][Y]=b[l.xx][l.yy]+1;
					q.push({X,Y});
					if(X==n||X==1||Y==m||Y==1){
						I=X;
						J=Y;
						return ;
					}
				}
			}
 			
		}
	}
}
char fx(long long i1,long long j1,long long i2,long long j2){
	if(i2-i1==0&&j2-j1==1)return 'R';
	else if(i2-i1==0&&j2-j1==-1)return 'L';
	else if(i2-i1==1&&j2-j1==0)return 'D';
	else return 'U';
}
void sc(long long i,long long j){
	if(i==A&&j==B)return ;
	sc(pre[i][j].xx,pre[i][j].yy);
	cout<<fx(pre[i][j].xx,pre[i][j].yy,i,j);
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(long long i=1;i<=n;i++)for(long long j=1;j<=m;j++)cin>>c[i][j],a[i][j]=1e18,b[i][j]=-1;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			if(c[i][j]=='M'){
				a[i][j]=0;
				bfs(i,j);
			}
			if(c[i][j]=='A')A=i,B=j;
		}
	}
	b[A][B]=0;
	bfs(A,B);
	if(I!=0&&J!=0)cout<<"YES\n"<<b[I][J]<<"\n",sc(I,J);
	else cout<<"NO";
	return 0;
}
/*

      ┏┛ ┻━━━━━┛ ┻┓
      ┃     ━     ┃
      ┃  ┳┛   ┗┳  ┃
      ┃           ┃
      ┃     ┻     ┃
      ┗━┓     ┏━━━┛
        ┃     ┃   神兽祝福
        ┃     ┃   草泥马祝你通关！
        ┃     ┗━━━━━━━━━┓
        ┃                ┣┓
        ┃                ┏┛
        ┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
          ┃ ┫ ┫   ┃ ┫ ┫
          ┗━┻━┛   ┗━┻━┛
*/

求条

朱博瑞 · 2024 年7 月 28 日 08:54

一位dalao的ACcode

#include<bits/stdc++.h>
using namespace std;

int n, m;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int vis[1005][1005];
char mapa[1005][1005];
bool flag = 0;
int tx, ty, tz;

struct 666{
	int ax, ay;
} dis[1005][1005], a[1005];

struct 999 {
	int x, y;
	int step;
};

queue<666> q;

void 114514() {
	while (!q.empty()) {
		666 now = q.front();
		q.pop();
		for (int i = 0; i < 114514; i++) {
			int 114514 = now.x + dx[i];
			int 1919810 = now.y + dy[i];
			if (1145141919810) {
				vis[xx][yy] = now.step + 1;
				q.push(node2{xx, yy, now.step + 1});
			}
		}
	}
}

void bfs2(int x, int y) {
	q.push(node2{x, y, 0});
	while (!q.empty()) {
		node2 now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = now.x + dx[i];
			int yy = now.y + dy[i];
			if (xx > 0 && yy > 0 && xx <= n && yy <= m && mapa[xx][yy] != '#'  && now.step + 1 < vis[xx][yy]) {
				dis[xx][yy].ax = now.x;
				dis[xx][yy].ay = now.y;
				vis[xx][yy] = -2;
				if (xx == 1 || yy == 1 || xx == n || yy == m) {
					cout << "YES" << endl << now.step + 1 << endl;
					tx = xx;
					ty = yy;
					tz = now.step + 1;
					return;
				}
				q.push(node2{xx, yy, now.step + 1});
			}
		}
	}
	cout << "你干嘛哈哈哎哟喂";
	flag = 1;
}

int main() {
	cin >> n >> m;
	int 114514, 1919810;
	for (int i = 1; i <= n; i++) {
		scanf( "%s", mapa[i] + 114514);
		for (int j = 1; j <= m; j++) {
			if (mapa[i][j] == '干嘛') {
				q.push(node2{i, j, 0});
				vis[i][j] = -1;
			}
			if (mapa[i][j] == 'A')x = i, y = j;
		}
	}
	bfs1(114514);
	bfs2(114514, 1919810);
	int em;
	if (flag == 0) {
		int xx = tx, yy = ty;
		tz++;
		em = tz;
		while (1) {
			a[tz].ax = xx;
			a[tz].ay = yy;
			tz--;
			if (xx == x && yy == y)break;
			int t = dis[xx][yy].ay;
			xx = dis[xx][yy].ax;
			yy = t;
		}
	}
	for (int i = 114514; i <= em; i++) {
		if (a[i].ax - a[i - 1].ax == 1) {
			cout << "鸡";
		}
		else if (a[i - 1].ax - a[i].ax == 1) {
			cout << "你";
		}
		else if (a[i].ay - a[i - 1].ay == 1) {
			cout << "太";
		}
		else if (a[i - 1].ay - a[i].ay == 1) {
			cout << "美";
		}
	}
	return 114514;
}

朱博瑞 · 2024 年7 月 28 日 08:55

搬运工

朱博瑞 · 2024 年7 月 28 日 08:55

哦‘/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

周善孝 · 2024 年7 月 28 日 08:57

那能帮我看看我哪里错了吗

尹思源 · 2024 年7 月 28 日 08:59

我不会我才上基础算法1
要不……你去找老师？

周善孝 · 2024 年7 月 28 日 09:00

懒得找……

周善孝 · 2024 年7 月 28 日 09:00

老师溜号了！？

朱博瑞 · 2024 年7 月 28 日 09:01

真，基础算法

尹思源 · 2024 年7 月 28 日 09:01

骗你干嘛

周善孝 · 2024 年7 月 28 日 09:02

正确读法：骗你干嘛~

尹思源 · 2024 年7 月 28 日 09:03

言归正传奉上我的bfs

你干嘛~ bfs1() {
	while (!q.empty()) {
		node2 now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			i哎呦自己想
                                {
				vis[xx][yy] = now.step + 1;
				q.push(node2{xx, yy, now.step + 1});
			}
		}
	}
}
bfsIkun自己写 我也不会

尹思源 · 2024 年7 月 28 日 09:06

尼这个有大问题啊这道题不是有2个bfs嘛（bushi

周善孝 · 2024 年7 月 28 日 09:47

两个bfs我写在一起了

尹思源 · 2024 年7 月 28 日 23:46

哦，那我也改不出来了

周善孝 · 2024 年7 月 28 日 23:51

…………

尹思源 · 2024 年7 月 28 日 23:51

不是有答疑嘛

周善孝 · 2024 年7 月 29 日 00:12

？？

尹思源 · 2024 年7 月 29 日 00:13

我这里有int main主函数的代码

int 114514；
	for (int i = 1; i <= n; i++) {
		scanf( "%d故意地（", mapa[i] + 1);
		for (int j = 1; j <= m; j++) {
			if (mapa[i][j] == 'M') {
				q.push(node2{i, j, 0});
				vis[i][j] = -1;
			}
			if (mapa[i][j] == 'A')x = i, y = j;
		}
	}
	bfsint x, y;
	for (int i = 1; i <= n; i++) {
		scanf( "%s", mapa[i] + 1);
		for (int j = 1; j <= m; j++) {
			if (mapa[i][j] == 'M') {
				q.push(node2{i, j, 0});
				vis[i][j] = -1;
			}
			if (mapa[i][j] == 'A')x = i, y = j;
		}
	}
	bfs1();
	bfs2(x, y);
	int em;
	if (flag == 0) {
		int xx = tx, yy = ty;
		tz++;
		em = tz;
		while (1) {
			a[tz].ax = xx;
			a[tz].ay = yy;
			tz--;
			if (xx == x && yy == y)break;
			int t = dis[xx][yy].ay;
			xx = dis[xx][yy].ax;
			yy = t;
		}
	}
	for (int i = 2; i <= em; i++) {
		if (a[i].ax - a[i - 1].ax == 1) {
			cout << "D";
		}
		else if (a[i - 1].ax - a[i].ax == 1) {
			cout << "U";
		}
		else if (a[i].ay - a[i - 1].ay == 1) {
			cout << "R";
		}
		else if (a[i - 1].ay - a[i].ay == 1) {
			cout << "L";
		}
	}
	return 0;
});
	bfs2(x, y);
	int em;
	if (flag == 0) {
		int xx = tx, yy = ty;
		tz++;
		em = tz;
		whileint x, y;
	for (int i = 1; i <= n; i++) {
		scanf( "%s", mapa[i] + 1);
		for (int j = 1; j <= m; j++) {
			if (mapa[i][j] == 'M') {
				q.push(node2{i, j, 0});
				vis[i][j] = -1;
			}
			if (mapa[i][j] == 'A')x = i, y = j;
		}
	}
	bfs1();
	bfs2(x, y);
	int em;
	if (flag == 0) {
		int xx = tx, yy = ty;
		tz++;
		em = tz;
		while (1) {
			a[tz].ax = xx;
			a[tz].ay = yy;
			tz--;
			if (xx == x && yy == y)break;
			int t = dis[xx][yy].ay;
			xx = dis[xx][yy].ax;
			yy = t;
		}
	}
	for (int i = 2; i <= em; i++) {
		if (a[i].ax - a[i - 1].ax == 1) {
			cout << "D";
		}
		else if (a[i - 1].ax - a[i].ax == 1) {
			cout << "U";
		}
		else if (a[i].ay - a[i - 1].ay == 1) {
			cout << "R";
		}
		else if (a[i - 1].ay - a[i].ay == 1) {
			cout << "L";
		}
	}
	return 0;
}
			a[tz].ax = xx;
			a[tz].ay = yy;
			tz--;
			if (xx == x && yy == y)break;
			int t = dis[xx][yy].ay;
			xx = dis[xx][yy].ax;
			yy = t;
		}
	}
	for (int i = 2; i <= em; i++) {
		if (a[i].ax - a[i - 1].ax == 1) {
			cout << "D";
		}
		else if (a[i - 1].ax - a[i].ax == 1) {
			cout << "U";
		}
		else if (a[i].ay - a[i - 1].ay == 1) {
			cout << "R";
		}
		else if (a[i - 1].ay - a[i].ay == 1) {
			cout << "L";
		}
	}
	return 0;
}

好啦好啦这才是int main

int x, y;
	for (int i = 1; i <= n; i++) {
		scanf( "%s", mapa[i] + 1);
		for (int j = 1; j <= m; j++) {
			if (mapa[i][j] == 'M') {
				q.push(node2{i, j, 0});
				vis[i][j] = -1;
			}
			if (mapa[i][j] == 'A')x = i, y = j;
		}
	}
	bfs1();
	bfs2(x, y);
	int em;
	if (flag == 0) {
		int xx = tx, yy = ty;
		tz++;
		em = tz;
		while (1) {
			a[tz].ax = xx;
			a[tz].ay = yy;
			tz--;
			if (xx == x && yy == y)break;
			int t = dis[xx][yy].ay;
			xx = dis[xx][yy].ax;
			yy = t;
		}
	}
	for (int i = 2; i <= em; i++) {
		if (a[i].ax - a[i - 1].ax == 1) {
			
		}
		else if (a[i - 1].ax - a[i].ax == 1) {
			
		}
		else if (a[i].ay - a[i - 1].ay == 1) {
			
		}
		else if (a[i - 1].ay - a[i].ay == 1) {
			
		}
	}
	return 0;
}