比赛 板子大赛 评测结果 AAAAAAAAAA
题目名称 走迷宫 最终得分 100
用户昵称 xxz 运行时间 0.031 s
代码语言 C++ 内存使用 3.50 MiB
提交时间 2025-01-22 14:52:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int m,n,sx,sy,fx,fy;
int dy[5]={0,0,-1,1,0},dx[5]={0,-1,0,0,1};
int roadnum;
int mp[20][20];
bool vis[20][20];
struct Node{
	int x;int y;
};
Node son[20][20];//下标是爹,内容是儿子
void printroad(Node f){
	if(son[f.x][f.y].x==-1)return;
	printf("(%d,%d)->",f.x,f.y);
	printroad(son[f.x][f.y]);
	return;
}
void dfs(Node x){
	vis[sx][sy]=1;
	if(x.x==fx&&x.y==fy){
		roadnum++;
		son[x.x][x.y]={-1,-1};
		printroad({sx,sy});
		printf("(%d,%d)\n",fx,fy);
//		for(int i=1;i<=16;i++)for(int j=1;j<=16;j++)son[i][j]={0,0};
		return;
	}
	for(int i=1;i<=4;i++){
		int xx=x.x+dx[i],yy=x.y+dy[i];
		if(xx<1||xx>m||yy<1||yy>n||vis[xx][yy]||!mp[xx][yy])continue;
		son[x.x][x.y]={xx,yy};
		
//		printf("%d %d\n",xx,yy);
		
		vis[xx][yy]=1;
		dfs({xx,yy});
		vis[xx][yy]=0;
	}
	return;
}
int main(){
	freopen("maize.in","r",stdin);freopen("maize.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&mp[i][j]);
		}
	}
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
	dfs({sx,sy});
	if(roadnum<1)printf("-1");
	return 0;
}