[question 21] idiom Solitaire (Beijing Institute of Technology / Beijing University of Technology / programming methods and practice / primary school)

Catalog

Preface

Reference material

  Ideas

Initial code

Fix code

---

Preface

This problem is typical bfs, But you need to build your own diagram , So it's a little more difficult .

Reference material

First, learn the relevant knowledge of the following figure , Definition of graph , Two representations , Two search algorithms BFS and DFS：

A detailed explanation of the picture _Lin-Cheng The blog of -CSDN Blog

And that is map,queue,vector The concept and usage of , On csdn Just search

  Ideas

use map and vector Combine to construct the graph structure in the form of adjacency linked list .

Specifically , use map The subscript is the end of the idiom , Corresponding to this subscript vector It stores the end of all idioms that begin with this end .

With pictures, it is classic bfs It's the link .

Initial code

wa 了 2 Hair , The preliminary guess is that the system is wrong , When I did this, I felt a little uneasy , The fact proved that , What could happen , In front of enough data , It must happen .

#include<cstdio>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#define SIZE 1000010
// The rationality of simply subscribing to the end ：
int step[SIZE];
bool vis[SIZE];
int main(void)
{
	//	freopen("input.txt", "r", stdin);
	int i, m,
		temp1, temp2, s1, s2, s3, s4, e1, e2, e3, e4;
	std::map<int, std::vector<int>> gragh;
	std::queue<int> q;
	// Read the beginning and end of all given idioms , Structure ; Read all the beginning and ending idioms 
	scanf("%d", &m);
	scanf("%*d %*d %*d %*d");// Clear the first word to prevent interference 
	for (i = 1; i < m; i++)
	{
		scanf("%d %*d %*d %d", &temp1, &temp2);
		gragh[temp1].push_back(temp2);
	}
	scanf("%d %d %d %d", &s1, &s2, &s3, &s4);
	scanf("%d %d %d %d", &e1, &e2, &e3, &e4);
	// Judge whether it is self looping 
	if (s1 == e1 && s2 == e2 && s3 == e3 && s4 == e4)
	{
		printf("1\n");// Directly output from the loop 
		return 0;
	}
	else // It's not self circulation bfs
	{
		memset(step, -1, sizeof step);
		memset(vis, false, sizeof vis);
		q.push(s4);
		vis[s4] = true;
		step[s4] = 1;
		while (!q.empty())
		{
			// Out of the team , first top Should be s4
			int top = q.front();
			q.pop();
			// Into the top The next layer of 
			for (auto x : gragh[top])// Traverse vector,
			{
				if (!vis[x])
				{
					q.push(x);
					vis[x] = true; // Add access tags 
					step[x] = step[top] + 1; // Go to the x The number of steps is to walk to top The next step in the number of steps 
                    if (x == e4)
						break; // Because it's layer by layer , So once found , It must be optimal 
				}
			}
		}
		printf("%d\n", step[e4]);
		return 0;
	}
}

Fix code

The excited heart , Shaking hand ！

AC La ！

unexpected , understandable .

There is a system error in the previous code ：

To save space , A one-dimensional array is used to store whether the state has been accessed , But the subscript is the end , Don't care at the beginning ？

If you ignore the beginning , There will be false endings found in advance , such as ：

6

1 2 3 4
4 6 7 10
4 5 6 7
7 8 9 10
4 6 6 1
1 6 8 8

1 2 3 4
7 8 9 10

Normal should be 1234  4567  789 10 But there is one 467 10, Will find it in advance , Output 2, So add a judgment that judges both the beginning and the end , This will be output 3.

if (top == e1 && x == e4)
	break;

But there will be another situation , I found a false ending , We don't know break, But the ending represents visit and step Affected , In the future, there will be a real end , Because I have visited , So I skipped , So the false ending needs to be repaired .

if (top != e1 && x == e4)
{
	vis[x] = false;
	step[x]--;
}

Do the above two points , It completely solves the impact of using one-dimensional arrays .

#include<cstdio>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#define SIZE 1000010
// The rationality of simply subscribing to the end ： If no measures are taken , There may be , Different beginning , Interference occurs in nodes with the same end 
int step[SIZE];
bool vis[SIZE];
int main(void)
{
	freopen("input.txt", "r", stdin);
	int i, m,
		temp1, temp2, s1, s2, s3, s4, e1, e2, e3, e4;
	std::map<int, std::vector<int>> gragh;
	std::queue<int> q;
	// Read the beginning and end of all given idioms , Structure ; Read all the beginning and ending idioms 
	scanf("%d", &m);
	for (i = 0; i < m; i++)
	{
		scanf("%d %*d %*d %d", &temp1, &temp2);
		gragh[temp1].push_back(temp2);
	}
	scanf("%d %d %d %d", &s1, &s2, &s3, &s4);
	scanf("%d %d %d %d", &e1, &e2, &e3, &e4);
	// Judge whether it is self looping 
	if (s1 == e1 && s2 == e2 && s3 == e3 && s4 == e4)
	{
		printf("1\n");// Directly output from the loop 
		return 0;
	}
	else // It's not self circulation bfs
	{
		memset(step, -1, sizeof step);
		memset(vis, false, sizeof vis);
		q.push(s4);
		vis[s4] = true;
		step[s4] = 1;
		while (!q.empty())
		{
			// Out of the team , first top Should be s4
			int top = q.front();
			q.pop();
			// Into the top The next layer of 
			for (auto x : gragh[top])// Traverse vector,
			{
				if (!vis[x])
				{
					q.push(x);
					vis[x] = true; // Add access tags 
					step[x] = step[top] + 1; // Go to the x The number of steps is to walk to top The next step in the number of steps 
					if (top != e1 && x == e4)// Fix the effect of false endings 
					{
						vis[x] = false;
						step[x]--;
					}
					if (top == e1 && x == e4) // Because it's layer by layer , So once found , It must be optimal 
						break;
				}
			}
		}
		printf("%d\n", step[e4]);
		return 0;
	}
}