啊哈算法之水管工游戏

先给不同状态的水管编给号吧

跟走迷宫一样的，深搜，每个dfs里遍历水管的状态，如果当前状态和水管指向的下一个状态能连通就深搜过去直到走到终点为止
上代码吧,这个代码是加强版，支持了更多的水管的编号，已经出口，入口和出发点是由用户输入的，以后可以用python做7k7k的水管工游戏辅助哈哈
游戏地址

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define Max 10
typedef struct suiguan {
	int type;
	int lt[4 + 1];
}sNode;
typedef struct {
	int x;
	int y;
}mNode;
mNode stack[Max*2];
int tail=0;
int m, n;
sNode map[Max + 2][Max + 2];
int book[Max + 2][Max + 2];
int ansFlag = 0;
int _x[3 + 1];
int _y[3 + 1];
int _type[3 + 1];


int move[4 + 1][2] = {
{ 0, 0 },
{ 0, -1 },
{ -1, 0 },
{ 0, 1 },
{ 1, 0},
};

void display() {
	for (int i = 0; i <= m+1; i++){
		for (int j = 0; j <= n+1; j++){
			printf("%d\t",map[i][j].type);
		}
		printf("\n");
	}
}
sNode creat(int type) {
	sNode* shuiguan = (sNode*)malloc(sizeof(sNode)*(10+1));
	for (int i = 0; i <= 10; i++){
		memset(shuiguan[i].lt, 0, sizeof(int) * 5);
		shuiguan[i].type = i;
	}
	shuiguan[1].lt[2] = shuiguan[1].lt[3] = 1;
	shuiguan[2].lt[3] = shuiguan[2].lt[4] = 1;
	shuiguan[3].lt[1] = shuiguan[3].lt[4] = 1;
	shuiguan[4].lt[1] = shuiguan[4].lt[2] = 1;
	shuiguan[5].lt[1] = shuiguan[5].lt[3] = 1;
	shuiguan[6].lt[2] = shuiguan[6].lt[4] = 1;
	shuiguan[7].lt[1] = shuiguan[7].lt[3] = shuiguan[7].lt[4] = 1;
	shuiguan[8].lt[1] = shuiguan[8].lt[2] = shuiguan[8].lt[4] = 1;
	shuiguan[9].lt[1] = shuiguan[9].lt[2] = shuiguan[9].lt[3] = 1;
	shuiguan[10].lt[2] = shuiguan[10].lt[3] = shuiguan[10].lt[4] = 1;
	return shuiguan[type];
}
int check(int x, int y, int oldX, int oldY ,mNode* newNode,int* tailN) {
	int flag1 = 0;//代表着从旧节点能否到达当前节点
	int flag2 = 0;//代表着从当前节点能否到达旧节点
	int flag3 = 0;//代表着从当前节点能否到达新节点
	int flag4 = 0;//代表着从新节点能否到达当前节点

	for (int i = 1; i <= 4; i++){
		int temX= oldX, temY= oldY;
		if (map[oldX][oldY].lt[i]) {
			temX += move[i][0];temY += move[i][1];
			if (temX >= 0 && temX <= m+1 && temY >= 0 && temY <= n + 1 && map[temX][temY].type!=0 && map[temX][temY].type != -1)
				if (&map[temX][temY] == &map[x][y]) {
				flag1 = 1;
				break;
				}
		}
	}
	if (!flag1)return 0;
	for (int i = 1; i <= 4; i++) {
		int temX = x, temY = y;
		if (map[x][y].lt[i]) {
			temX += move[i][0]; temY += move[i][1];
			if (temX >= 0 && temX <= m+1 && temY >= 0 && temY <= n + 1 && map[temX][temY].type != 0 && map[temX][temY].type != -1)
				if (&map[temX][temY] == &map[oldX][oldY]) {
				flag2 = 1;
				}else {
				//如果(x,y)能与(oldX,oldY)连通，那么它有至多两个方向能到新节点
				//可是新节点又不一定能够和当前节点连接
				//但是这里不用管
				//现在出现了新的情况，有的水管能连通两个
					flag3 = 1;
					newNode[*tailN].x = temX; newNode[*tailN].y = temY; (*tailN)++;
				}
		}
	}
	if (!flag2)return 0;
	return 1;
	//flag3是一定成立的

}
int dfs(int step, int x, int y, int oldX, int oldY);
int check2(int step,int x, int y, int oldX, int oldY) {
	mNode newNode[2];
	int tailN = 0;
	if (check(x, y, oldX, oldY, newNode, &tailN)) {
		for (int i = 0; i < tailN; i++) {
			int newX = newNode[i].x, newY = newNode[i].y;
			if (!book[newX][newY]) {
				book[newX][newY] = 1;
				stack[tail].x = newX; stack[tail].y = newY;
				tail++;
				dfs(step + 1, newX, newY, x, y);
				book[newX][newY] = 0;
				if (ansFlag)return 1;
				tail--;
			}
		}
	}
}
int dfs(int step,int x,int y,int oldX,int oldY) {
	if (x == _x[2] && y == _y[2]) {
		ansFlag = 1;
		for (int i = 0; i <= tail-2; i++){
			printf("(%d,%d)",stack[i].x, stack[i].y);
		}
		return 1;
	}
	if (ansFlag)return 1;
	if (map[x][y].type == 0)return 0;

	if (map[x][y].type <= 4) {
		for (int i = 1; i <= 4; i++){
			map[x][y] = creat(i);
			check2(step, x, y, oldX, oldY);
		}
	}else if (map[x][y].type <= 6) {
		for (int i = 5; i <= 6; i++) {
			map[x][y] = creat(i);
			check2(step, x, y, oldX, oldY);
		}
	}else if (map[x][y].type <= 10) {
		for (int i = 7; i <= 10; i++) {
			map[x][y] = creat(i);
			check2(step, x, y, oldX, oldY);
		}
	}

}
int main(){
	printf("please input the map size\n");
	scanf("%d%d", &m, &n);
	printf("Please input the outlet, the first point connected with the entrance(x,y,type)3's\n");
	//1入口
	//2出口
	//3出发点
	for (int i = 1; i <= 3; i++){
		scanf("%d%d%d", &_x[i], &_y[i], &_type[i]);
		map[_x[i]][_y[i]] = creat(_type[i]);
	}
	for (int i = 1; i <= m; i++){
		for (int j = 1; j <= n; j++) {
			scanf("%d",&map[i][j].type);
			if (!map[i][j].type) {
				book[i][j] = map[i][j].type = -1;
				continue;
			}
			map[i][j] = creat(map[i][j].type);
		}
	}
	display();
	book[_x[3]][_y[3]] = 1;stack[tail].x = _x[3]; stack[tail].y = _y[3]; tail++;
	dfs(0, _x[3], _y[3], _x[1], _y[1]);
	if (ansFlag) {
		return 0;
	}
	else printf("impossible");
    return 0;
}