DFS T #9求助
查看原帖
DFS T #9求助
523541
wdy1028楼主2021/10/8 16:03
#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define mem(x,val) memset((x),(val),(sizeof(x)))
using namespace std;
const int INF = 1<<31-1;
char a[120][120];
int vis[120][120],res[100005][2],r,c,down;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
inline void dfs(int x,int y)
{
	if(x == r && y == c)
	{
		for(int i = 0;i < down;++i)
			printf("%d %d\n",res[i][0],res[i][1]);
		printf("%d %d\n",r,c);
		exit(0);
	}
	for(int i = 0;i < 4;++i)
	{
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(1 <= nx && nx <= r && 1 <= ny && ny <= c && !vis[nx][ny] && a[nx][ny] != '*')
		{
			res[down][0] = x;
			res[down][1] = y;
			++down;
			vis[nx][ny] = 1;
			dfs(nx,ny);
			vis[nx][ny] = 0;
			--down;
		}
	}
}
inline LL read()
{
	LL x=0,f=1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
	while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
	return f*x;
}
int main(int argc,char *argv[])
{ 
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);	
	r = read(),c = read();
	for(int i = 1;i <= r;++i)
		for(int j = 1;j <= c;++j) cin>>a[i][j];
	dfs(1,1);
	//printf("Tide used = %.0lf.ds\n",((double)clock()/(double)CLOCKS_PER_SEC) * 1000.0);
	return 0;
}  
2021/10/8 16:03
加载中...