90分,tle,求调
查看原帖
90分,tle,求调
1429782
hychouyichen楼主2024/8/25 11:23
#include<bits/stdc++.h>
using namespace std;
const int N=200;
int r,c,cnt=1;
char a[N][N];
int vis[N][N];
bool flag=false;
pair<int,int> vec[N*N];
void pop(){
	cnt--;
}
void push(pair<int,int> in){
	vec[cnt]=in;
	cnt++;
}
int mx[]={0,0,1,0,-1};
int my[]={0,-1,0,1,0};
void dfs(int x,int y){
	if(x==r&&y==c){
		flag=true;
		return ;
	}
	for(int i=1;i<=4;i++){
		int dx=x+mx[i],dy=y+my[i];
		if(dx<1||dx>r||dy<1||dy>c) continue; 
		if(vis[dx][dy]||a[dx][dy]=='*'){
			continue;
		}
		vis[dx][dy]=1;
		pair<int,int> in;
		in.first=dx;
		in.second=dy;
		push(in);
		dfs(dx,dy);
		if(flag) return; 
		vis[dx][dy]=0;
		pop();
	}
}
int main(){
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>a[i][j];
		}
	}
	vis[1][1]=1;
	dfs(1,1);
	cout<<1<<" "<<1<<endl;
	for(int i=1;i<cnt;i++){
		cout<<vec[i].first<<" "<<vec[i].second;
		cout<<endl;
		
	}

	return 0;
} 
2024/8/25 11:23
加载中...