[Jizhong] July 16, 2022 1432. Oil pipeline

Original title website

For some reason , This website will be inaccessible …

Title Description

Please help design a city $M$ To the city $Z$ Oil pipeline , Now the whole area has been divided into $R$ That's ok $C$ Column , Each cell may be empty or the following $7$ One of the basic pipelines ：
Oil from the city $M$ flow $Z$,“$+$” Type a pipe is special , Because oil must be in two directions （ Vertical and horizontal ） Up transfer , As shown in the figure below ：

Now the terrorists have got the design of the oil pipeline , And stole the pipe in one of the cells , Please help find the location and shape of the stolen pipe .

Format

Input format

The first $1$ Line inclusion $2$ It's an integer $R$ and $C$.
Next $R$ Every line $C$ Characters describe the shape after being stolen , The characters are divided into the following $3$ Kind of ：

1. “$.$” Said empty ;
2. character “$|$”（$ASCII$ by $124$）、“$-$”、“$+$”、“$1$”、“$2$”、“$3$”、“$4$” Describe the shape of the pipe ;
3. “$M$” and “$Z$” Representing City ,$2$ All of them only appear $1$ Time .

Input ensures that the flow direction of oil is unique , There is only one pipe with $M$ and $Z$ Connected to a , Besides , Make sure there are no extra pipes , That is to say, all the pipes will be used after being added to the stolen pipes .
The input is guaranteed to be solvable and unique .

Output format

Output the line number and column number of the stolen pipeline and the type of pipeline .

Examples

sample input

sample input 1

3 7
.......
.M-.-Z.
.......

sample input 2

3 5
..1-M
1-+..
Z.23.

sample input 3

6 10
Z.1----4..
|.|....|..
|..14..M..
2-+++4....
..2323....
..........

sample output

sample output 1

2 4 -

sample output 2

2 4 4

sample output 3

3 3 |

Tips

$1\le r,c\le 25$

Their thinking

There are many ways to solve this problem , Such as $bfs$、 Big simulation, etc .
Because the big simulation is simple and rough , Loved by myself , And I am too $lazy$, So there is no other algorithm .

Code

Warning

The following code is long and smelly , It may be life-threatening

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s;
char a[30][30];
bool check(char b[30][30],int x,int y,int f,int t) {
    
	while(b[x][y]!='Z') {
    
		t++;
		switch(b[x][y]) {
    
			case '-':{
    
				if(f==3) y--;
				else y++;
				break;
			}
			case '|':{
    
				if(f==1) x--;
				else x++;
				break;
			}
			case '+':{
    
				if(f==1) x--;
				else if(f==2) x++;
				else if(f==3) y--;
				else y++;
				break;
			}
			case '1':{
    
				if(f==1) {
    
					y++;
					f=4;
				}
				else {
    
					x++;
					f=2;
				}
				break;
			}
			case '2':{
    
				if(f==2) {
    
					y++;
					f=4;
				}
				else {
    
					x--;
					f=1;
				}
				break;
			}
			case '3':{
    
				if(f==2) {
    
					y--;
					f=3;
				}
				else {
    
					x--;
					f=1;
				}
				break;
			}
			case '4':{
    
				if(f==1) {
    
					y--;
					f=3;
				}
				else {
    
					x++;
					f=2;
				}
				break;
			}
			default:{
    
				return false;
			}
		}
	}
	return t-1==s;
}
bool test_left_down(int x,int y,int t) {
    
	if(a[x+1][y]=='.'&&(a[x+1][y-1]=='-'||a[x+1][y-1]=='+'||
	a[x+1][y-1]=='1'||a[x+1][y-1]=='2'||
	a[x+1][y-1]=='Z')) {
    
		a[x+1][y]='3';
		if(check(a,x+1,y,2,t)) {
    
			printf("%d %d 3",x+1,y);
			return true;
		}
		a[x+1][y]='+';
		if(check(a,x+1,y,2,t-1)) {
    
			printf("%d %d +",x+1,y);
			return true;
		}
		a[x+1][y]='.';
	}
	if(a[x][y-1]=='.'&&(a[x+1][y-1]=='|'||a[x+1][y-1]=='+'||
	a[x+1][y-1]=='2'||a[x+1][y-1]=='3'||
	a[x+1][y-1]=='Z')) {
    
		a[x][y-1]='1';
		if(check(a,x,y-1,3,t)) {
    
			printf("%d %d 1",x,y-1);
			return true;
		}
		a[x][y-1]='+';
		if(check(a,x,y-1,3,t-1)) {
    
			printf("%d %d +",x,y-1);
			return true;
		}
		a[x][y-1]='.';
	}
	return false;
}
bool test_left_up(int x,int y,int t) {
    
	if(a[x-1][y]=='.'&&(a[x-1][y-1]=='-'||a[x-1][y-1]=='+'||
	a[x-1][y-1]=='1'||a[x-1][y-1]=='2'||
	a[x-1][y-1]=='Z')) {
    
		a[x-1][y]='4';
		if(check(a,x-1,y,1,t)) {
    
			printf("%d %d 4",x-1,y);
			return true;
		}
		a[x-1][y]='+';
		if(check(a,x-1,y,1,t-1)) {
    
			printf("%d %d +",x-1,y);
			return true;
		}
		a[x-1][y]='.';
	}
	if(a[x][y-1]=='.'&&(a[x-1][y-1]=='|'||a[x-1][y-1]=='+'||
	a[x-1][y-1]=='1'||a[x-1][y-1]=='4'||
	a[x-1][y-1]=='Z')) {
    
		a[x][y-1]='2';
		if(check(a,x,y-1,3,t)) {
    
			printf("%d %d 2",x,y-1);
			return true;
		}
		a[x][y-1]='+';
		if(check(a,x,y-1,3,t-1)) {
    
			printf("%d %d +",x,y-1);
			return true;
		}
		a[x][y-1]='.';
	}
	return false;
}
bool test_right_down(int x,int y,int t) {
    
	if(a[x+1][y]=='.'&&(a[x+1][y+1]=='-'||a[x+1][y+1]=='+'||
	a[x+1][y+1]=='3'||a[x+1][y+1]=='4'||
	a[x+1][y+1]=='Z')) {
    
		a[x+1][y]='2';
		if(check(a,x+1,y,2,t)) {
    
			printf("%d %d 2",x+1,y);
			return true;
		}
		a[x+1][y]='+';
		if(check(a,x+1,y,2,t-1)) {
    
			printf("%d %d +",x+1,y);
			return true;
		}
		a[x+1][y]='.';
	}
	if(a[x][y+1]=='.'&&(a[x+1][y+1]=='|'||a[x+1][y+1]=='+'||
	a[x+1][y+1]=='2'||a[x+1][y+1]=='3'||
	a[x+1][y+1]=='Z')) {
    
		a[x][y+1]='4';
		if(check(a,x,y+1,4,t)) {
    
			printf("%d %d 4",x,y+1);
			return true;
		}
		a[x][y+1]='+';
		if(check(a,x,y+1,4,t-1)) {
    
			printf("%d %d +",x,y+1);
			return true;
		}
		a[x][y+1]='.';
	}
	return false;
}
bool test_right_up(int x,int y,int t) {
    
	if(a[x-1][y]=='.'&&(a[x-1][y+1]=='-'||a[x-1][y+1]=='+'||
	a[x-1][y+1]=='3'||a[x-1][y+1]=='4'||
	a[x-1][y+1]=='Z')) {
    
		a[x-1][y]='1';
		if(check(a,x-1,y,1,t)) {
    
			printf("%d %d 1",x-1,y);
			return true;
		}
		a[x-1][y]='+';
		if(check(a,x-1,y,1,t-1)) {
    
			printf("%d %d +",x-1,y);
			return true;
		}
		a[x-1][y]='.';
	}
	if(a[x][y+1]=='.'&&(a[x-1][y+1]=='|'||a[x-1][y+1]=='+'||
	a[x-1][y+1]=='1'||a[x-1][y+1]=='4'||
	a[x-1][y+1]=='Z')) {
    
		a[x][y+1]='3';
		if(check(a,x,y+1,4,t)) {
    
			printf("%d %d 3",x,y+1);
			return true;
		}
		a[x][y+1]='+';
		if(check(a,x,y+1,4,t-1)) {
    
			printf("%d %d +",x,y+1);
			return true;
		}
		a[x][y+1]='.';
	}
	return false;
}
bool test_down(int x,int y,int t) {
    
	if(test_left_down(x,y,t)) return true;
	if(test_right_down(x,y,t)) return true;
	if(a[x+1][y]=='.'&&(a[x+2][y]=='|'||a[x+2][y]=='+'||
	a[x+2][y]=='2'||a[x+2][y]=='3'||
	a[x+2][y]=='Z')) {
    
		a[x+1][y]='|';
		if(check(a,x+1,y,2,t)) {
    
			printf("%d %d |",x+1,y);
			return true;
		}
		a[x+1][y]='+';
		if(check(a,x+1,y,2,t-1)) {
    
			printf("%d %d +",x+1,y);
			return true;
		}
		a[x+1][y]='.';
	}
	return false;
}
bool test_up(int x,int y,int t) {
    
	if(test_left_up(x,y,t)) return true;
	if(test_right_up(x,y,t)) return true;
	if(a[x-1][y]=='.'&&(a[x-2][y]=='|'||a[x-2][y]=='+'||
	a[x-2][y]=='1'||a[x-2][y]=='4'||
	a[x-2][y]=='Z')) {
    
		a[x-1][y]='|';
		if(check(a,x-1,y,1,t)) {
    
			printf("%d %d |",x-1,y);
			return true;
		}
		a[x-1][y]='+';
		if(check(a,x-1,y,1,t-1)) {
    
			printf("%d %d +",x-1,y);
			return true;
		}
		a[x-1][y]='.';
	}
	return false;
}
bool test_right(int x,int y,int t) {
    
	if(test_right_up(x,y,t)) return true;
	if(test_right_down(x,y,t)) return true;
	if(a[x][y+1]=='.'&&(a[x][y+2]=='-'||a[x][y+2]=='+'||
	a[x][y+2]=='3'||a[x][y+2]=='4'||
	a[x][y+2]=='Z')) {
    
		a[x][y+1]='-';
		if(check(a,x,y+1,4,t)) {
    
			printf("%d %d -",x,y+1);
			return true;
		}
		a[x][y+1]='+';
		if(check(a,x,y+1,4,t-1)) {
    
			printf("%d %d +",x,y+1);
			return true;
		}
		a[x][y+1]='.';
	}
	return false;
}
bool test_left(int x,int y,int t) {
    
	if(test_left_down(x,y,t)) return true;
	if(test_left_up(x,y,t)) return true;
	if(a[x][y-1]=='.'&&(a[x][y-2]=='-'||a[x][y-2]=='+'||
	a[x][y-2]=='1'||a[x][y-2]=='2')) {
    
		a[x][y-1]='-';
		if(check(a,x,y-1,3,t)) {
    
			printf("%d %d -",x,y-1);
			return true;
		}
		a[x][y-1]='+';
		if(check(a,x,y-1,3,t-1)) {
    
			printf("%d %d +",x,y-1);
			return true;
		}
		a[x][y-1]='.';
	}
	return false;
}
void work(int x,int y,int f,int t) {
    
	t++;
	switch(a[x][y]) {
    
		case 'M':{
    
			t--;
			if(a[x-1][y]=='|'||a[x-1][y]=='1'||
			a[x-1][y]=='4'||a[x-1][y]=='+') {
    
				f=1;
				work(x-1,y,f,t);
			}
			else if(a[x+1][y]=='|'||a[x+1][y]=='2'||
			a[x+1][y]=='3'||a[x-1][y]=='+') {
    
				f=2;
				work(x+1,y,f,t);
			}
			else if(a[x][y-1]=='-'||a[x][y-1]=='+'||
			a[x][y-1]=='1'||a[x][y-1]=='2') {
    
				f=3;
				work(x,y-1,f,t);
			}
			else if(a[x][y+1]=='-'||a[x][y+1]=='+'||
			a[x][y+1]=='3'||a[x][y+1]=='4') {
    
				f=4;
				work(x,y+1,f,t);
			}
			else {
    
				if(test_left(x,y,t)) return;
				if(test_right(x,y,t)) return;
				if(test_up(x,y,t)) return;
				if(test_down(x,y,t)) return;
			}
			break;
		}
		case '|':{
    
			if(f==1) {
    
				if(a[x-1][y]!='.') work(x-1,y,f,t);
				else {
    
					test_up(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x+1][y]!='.') work(x+1,y,f,t);
				else {
    
					test_down(x,y,t);
					return;
				}
			}
			break;
		}
		case '-':{
    
			if(f==3) {
    
				if(a[x][y-1]!='.') work(x,y-1,f,t);
				else {
    
					test_left(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x][y+1]!='.') work(x,y+1,f,t);
				else {
    
					test_right(x,y,t);
					return;
				}
			}
			break;
		}
		case '+':{
    
			if(f==1) {
    
				if(a[x-1][y]!='.') work(x-1,y,f,t);
				else {
    
					test_up(x,y,t);
					return;
				}
			}
			else if(f==2) {
    
				if(a[x+1][y]!='.') work(x+1,y,f,t);
				else {
    
					test_down(x,y,t);
					return;
				}
			}
			else if(f==3) {
    
				if(a[x][y-1]!='.') work(x,y-1,f,t);
				else {
    
					test_left(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x][y+1]!='.') work(x,y+1,f,t);
				else {
    
					test_right(x,y,t);
					return;
				}
			}
			break;
		}
		case '1':{
    
			if(f==1) {
    
				if(a[x][y+1]!='.') work(x,y+1,4,t);
				else {
    
					test_right(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x+1][y]!='.') work(x+1,y,2,t);
				else {
    
					test_down(x,y,t);
					return;
				}
			}
			break;
		}
		case '2':{
    
			if(f==2) {
    
				if(a[x][y+1]!='.') work(x,y+1,4,t);
				else {
    
					test_right(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x-1][y]!='.') work(x-1,y,1,t);
				else {
    
					test_up(x,y,t);
					return;
				}
			}
			break;
		}
		case '3':{
    
			if(f==2) {
    
				if(a[x][y-1]!='.') work(x,y-1,3,t);
				else {
    
					test_left(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x-1][y]!='.') work(x-1,y,1,t);
				else {
    
					test_up(x,y,t);
					return;
				}
			}
			break;
		}
		case '4':{
    
			if(f==1) {
    
				if(a[x][y-1]!='.') work(x,y-1,3,t);
				else {
    
					test_left(x,y,t);
					return;
				}
			}
			else {
    
				if(a[x+1][y]!='.') work(x+1,y,2,t);
				else {
    
					test_down(x,y,t);
					return;
				}
			}
			break;
		}
	}
}
signed main() {
    
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=n;i++) {
    
		for(int j=1;j<=m;j++) {
    
			cin>>a[i][j];
			if(a[i][j]=='M') {
    
				x=i,y=j;
			}
			else if(a[i][j]!='.'&&a[i][j]!='Z') s++;
			if(a[i][j]=='+') s++;
		}
	}
	work(x,y,0,0);
	return 0;
}

Copyright

Icons provided by Bootstrap