---
# System prepended metadata

title: Jumping Array  Puzzle
tags: [花中Judge, C++]

---

# Jumping Array  Puzzle
[花中judge d001. Jumping Array Puzzle (題目連結)](https://judge.hlhs.hlc.edu.tw/ShowProblem?problemid=d001)

**BFS作法**
<font color="#00CE17">**AC**</font> **(90ms, 8.4MB)**
```cpp=
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define x first
#define y second

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	string begin, end;
	cin>>begin>>end;
	queue<pair<string, int>> q;
	set<string> s;
	q.push({begin, 0});
	int len=begin.size();
	int d[4]={-2, -1, 1, 2};
	while(!q.empty()){
		string now=q.front().x;
		int ct=q.front().y;
		q.pop();
		if(s.count(now)) continue;
		s.insert(now);
		for(int i=0; i<len; i++){
			for(int j=0; j<4; j++){
				int id=i+d[j];
				if(id>=0&&id<len){
					if(now[id]=='0'){
						string ts="";
						for(int k=0; k<len; k++){
							if(k!=id&&k!=i) ts+=now.substr(k, 1);
							else if(k==id) ts+=now.substr(i, 1);
							else ts+=now.substr(id, 1);
						}
						if(ts==end){
							cout<<ct+1;
							return 0;
						}
						q.push({ts, ct+1});
					}
				}	
			}
		}
	}
	
	return 0;
}
```
###### tags: `C++` `花中Judge`