Demo entry 6762923

py

   

Submitted by 反对法 on Oct 18, 2018 at 05:24
Language: Python 3. Code size: 1.4 kB.

/*****
*** #25 磊哥教你玩 Flow Free!
*** 
******/
#include <bits/stdc++.h>

using namespace std;

const int N = 10;
int colorNum;

int offset[][2]={
	0,1,//
	0,-1,//
	1,0,//
	-1,0//
};

char s[N][N];
int a[N][2];// 记录RGBY的一个端点的位置
//判断是否越过矩阵边界
bool is_ok(int x,int y){
	return 1<=x&&x<=4&&1<=y&&y<=4;
}

bool vis[N][N]={false};

bool dfs(int rt,int x,int y,int cnt){
	if(rt==colorNum+1) return cnt==16;// 连接好颜色端点相同无交叉的线路且覆盖所有的点
	
	for(int i=0;i<4;++i){
		int tx=x+offset[i][0];
		int ty=y+offset[i][1];
		if(!is_ok(tx,ty)||vis[tx][ty]||(s[tx][ty]!='W'&&s[tx][ty]!=s[a[rt][0]][a[rt][1]])) continue;
		                   // 越过边界or已经是其它水管的一部分了or它是其它颜色的端点)
		vis[tx][ty]=true;
		//找到了同颜色端点
		if(s[tx][ty]==s[a[rt][0]][a[rt][1]]){
			if(dfs(rt+1,a[rt+1][0],a[rt+1][1],cnt+1)) return true;//进行下一个管道的铺设
		}else{
			if(dfs(rt,tx,ty,cnt+1)) return true; 
		}
		vis[tx][ty]=false;
	}
	return false;
}
int main(){

	for(int i=1;i<=4;++i)
		scanf("%s",s[i]+1);
	colorNum=3;
	for(int i=1;i<=4;++i)
		for(int j=1;j<=4;++j)
			switch(s[i][j]){
				case 'W': break;
				case 'R': a[1][0]=i;a[1][1]=j;break;
				case 'G': a[2][0]=i;a[2][1]=j;break;
				case 'B': a[3][0]=i;a[3][1]=j;break;
				case 'Y': a[4][0]=i;a[4][1]=j; colorNum=4;break;
			}
	if(dfs(1,a[1][0],a[1][1],colorNum))
		puts("solvable");
	else puts("not solvable");
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).