为什么第九个超时?应该是回溯了呀
查看原帖
为什么第九个超时?应该是回溯了呀
545697
Augenstern_G楼主2021/10/3 11:20

到底是哪里的问题啊qwq

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

char k;
int dx[4]= {0,0,1,-1};
int dy[4]= {1,-1,0,0};
int r,c,vis[maxn][maxn],st[maxn][3],cnt,a[maxn][maxn];

void dfs(int x,int y) {
	if(x==r&&y==c) {
		for(int i=1; i<=cnt; i++) {
			cout<<st[i][1]<<" "<<st[i][2]<<endl;
		}
		exit(0);
	}
	for(int i=0; i<4; i++) {
		int tx=x+dx[i],ty=y+dy[i];
		if(a[tx][ty]==1&&vis[tx][ty]==0&&tx>=1&&tx<=r&&ty>=1&&ty<=c) {
			vis[tx][ty]=1;
			++cnt;
			st[cnt][1]=tx;
			st[cnt][2]=ty;
			dfs(tx,ty);
			cnt--;
			vis[tx][ty]=0;
		}
	}
}

int main() {
	cin>>r>>c;
	for(int i=1; i<=r; i++) {
		for(int j=1; j<=c; j++) {
			cin>>k;
			if(k=='.') a[i][j]=1;
			else a[i][j]=0;
		}
	}
	cout<<"1 1"<<endl;
	dfs(1,1);
	return 0;
}
2021/10/3 11:20
加载中...