困于环中的机器人
困于环中的机器人
存在循环只有两种情况:
(1)一轮循环之后,如果最终的朝向不是北方
(2)一轮循环之后,如果是朝向北方,并且位于原点
class Solution {
public boolean isRobotBounded(String instructions) {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
//定义起点,朝向
int x=0,y=0;int face=0;
for(int i=0;i<instructions.length();i++){
char ch=instructions.charAt(i);
if(ch=='L'){
face--;
}else if(ch=='R'){
face++;
}else{
//移动
// face=(face+4)%4;//可能出现连续'L',对应的face可能小于-4
if(face<0){
face=4+(face%4);
}
x+=dx[face%4];
y+=dy[face%4];
}
}
return face%4!=0||(x==0&&y==0);
}
}
二维矩阵中探测环
方式一:通过fill-flood改造
class Solution {
boolean flag=false;
public boolean containsCycle(char[][] grid) {
//通过回溯
int n=grid.length;
int m=grid[0].length;
boolean[][] vis=new boolean[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!vis[i][j]){
dfs(grid,i,j,i,j,vis);
if(flag) {
return true;
}
}
}
}
return false;
}
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public void dfs(char[][] grid,int start,int end,int curX,int curY,boolean[][] vis){
if(vis[curX][curY]){
flag=true;
return;
}
vis[curX][curY]=true;
for(int k=0;k<4;k++){
int a=curX+dx[k];
int b=curY+dy[k];
// System.out.println("a"+a+"==="+"b"+b);
if(a>=0&&a<grid.length&&b>=0&&b<grid[0].length&&grid[a][b]==grid[curX][curY]&&!(a==start&&b==end)){
dfs(grid,curX,curY,a,b,vis);
}
}
}
}
方式二:通过方向对搜索方向进行控制
class Solution {
boolean flag=false;
public boolean containsCycle(char[][] grid){
int n=grid.length;int m=grid[0].length;
boolean[][] vis=new boolean[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!vis[i][j]){
dfs(grid,i,j,grid[i][j],'L',vis);
if(flag){
return true;
}
}
}
}
return false;
}
public void dfs(char[][] grid,int start,int end,char ch,char from,boolean[][] vis){
if(start<0||start>=grid.length||end<0||end>=grid[0].length||grid[start][end]!=ch){
return;
}
if(vis[start][end]){
flag=true;
return;
}
vis[start][end]=true;
if(from!='L'){//如果不是从[start][end]左边过来的,可以到[start][end]左边[start][end-1]并且是从右边过来的
dfs(grid,start,end-1,ch,'R',vis);
}
if(from!='R'){
dfs(grid,start,end+1,ch,'L',vis);
}
if(from!='U'){
dfs(grid,start-1,end,ch,'D',vis);
}
if(from!='D'){
dfs(grid,start+1,end,ch,'U',vis);
}
}
}
方式三:通过并查集寻找矩阵环
为了避免重复添加边,可以每次只将当前位置上面和左边的位置,对应的边加入并查集
int[] father;
public boolean containsCycle(char[][] grid){
int n=grid.length;
int m=grid[0].length;
init(m*n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i>0&&grid[i][j]==grid[i-1][j]){
if(find(i*m+j)!=find((i-1)*m+j)){
father[find(i*m+j)]=find((i-1)*m+j);
}else{
return true;
}
}
if(j>0&&grid[i][j]==grid[i][j-1]){
if(find(i*m+j)!=find(i*m+j-1)){
father[find(i*m+j)]=find(i*m+j-1);
}else{
return true;
}
}
}
}
return false;
}
public void init(int n){
father=new int[n];
for(int i=0;i<n;i++){
father[i]=i;
}
}
public int find(int x){
if(x!=father[x]){
father[x]=find(father[x]);
}
return father[x];
}