90求助
查看原帖
90求助
1033674
ayf2192538031楼主2024/4/4 10:01

#9 TLE了

#include<bits/stdc++.h>
using namespace std;
struct pos{
	int x,y;
};
int r,c;
bool a[150][150],book[150][150];char rd;
stack<pos> s;
stack<pos> st;
void dfs(int x,int y){
	s.push({x,y});
	book[x][y]=1;
	if(x==r&&y==c){
		while(!s.empty()){
			st.push(s.top());
			s.pop();
		}
		while(!st.empty()){
			cout<<st.top().x<<" "<<st.top().y<<"\n";
			st.pop();
		}exit(0);
	}
	if((x>1)&&(!a[x-1][y])&&(!book[x-1][y])) dfs(x-1,y);
	if((x<r)&&(!a[x+1][y])&&(!book[x+1][y])) dfs(x+1,y);
	if((y>1)&&(!a[x][y-1])&&(!book[x][y-1])) dfs(x,y-1);
	if((y<c)&&(!a[x][y+1])&&(!book[x][y+1])) dfs(x,y+1);
	s.pop();
	book[x][y]=0;
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>rd;
			if(rd=='.'){
				a[i][j]=0;
			}
			else{
				a[i][j]=1;
			}
		}
	}
	dfs(1,1);
	return 0;
} 
2024/4/4 10:01
加载中...