SCU 4445 Right turn(dfs)题解

思路:离散化之后,直接模拟就行,标记vis开三维

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + ;
const ll mod = 1e8 + ;
struct node{
ll x, y;
}p[maxn];
int mp[maxn][maxn], turn_num, vis[maxn][maxn][], nn, mm;
ll x[maxn], y[maxn];
int dir[][] = {, , , -, -, , , };
//下,左,上,右
bool dfs(int xx, int yy, int turn){ //将要朝向turn
if(vis[xx][yy][turn]) return false;
vis[xx][yy][turn] = ;
int xxx = xx + dir[turn][], yyy = yy + dir[turn][];
if(xxx < || xxx > nn - || yyy < || yyy > mm - )
return true;
while(mp[xxx][yyy] != ){
if(vis[xxx][yyy][turn]) return false;
vis[xxx][yyy][turn] = ;
xxx += dir[turn][];
yyy += dir[turn][];
if(xxx < || xxx > nn - || yyy < || yyy > mm - )
return true;
} turn_num++;
return dfs(xxx - dir[turn][], yyy - dir[turn][], (turn + ) % );
} int main(){
int n, sx, sy;
while(scanf("%d", &n) != EOF){
turn_num = ;
memset(mp, , sizeof(mp));
memset(vis, , sizeof(vis));
for(int i = ; i < n; i++){
scanf("%lld%lld", &p[i].x, &p[i].y);
x[i] = p[i].x;
y[i] = p[i].y;
}
x[n] = , y[n] = , p[n].x = , p[n].y = ;
n++;
sort(x, x + n);
sort(y, y + n);
int num1 = unique(x, x + n) - x;
int num2 = unique(y, y + n) - y;
for(int i = ; i < n; i++){
int X, Y;
X = lower_bound(x, x + num1, p[i].x) - x;
Y = lower_bound(y, y + num2, p[i].y) - y;
if(p[i].x == && p[i].y == ){
sx = X, sy = Y;
}
else{
mp[X][Y] = ;
}
}
nn = num1, mm = num2;
bool flag = dfs(sx, sy, );
if(flag) printf("%d\n", turn_num);
else printf("-1\n");
}
return ;
}
/*
4
1 0
0 1
0 -1
-1 0
*/
上一篇:Nginx服务器编译添加SSL模块


下一篇:LeetCode 566. Reshape the Matrix (重塑矩阵)