Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

递归法枚举,时间125ms,最菜的做法

Posted by whutkjy at 2018-02-08 21:15:39 on Problem 1753
#include<iostream>
#include<stdio.h>
using namespace std;

bool Check(bool maps[4][4])
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (maps[i][j] != maps[0][0])
			{
				return false;
			}
		}
	}
	return true;
}

void Flip(int index, bool maps[4][4])
{
	int r = index / 4;
	int c = index % 4;
	if (r > 0)
	{
		maps[r - 1][c] = !maps[r - 1][c];
	}
	if (r < 3)
	{
		maps[r + 1][c] = !maps[r + 1][c];
	}
	if (c > 0)
	{
		maps[r][c - 1] = !maps[r][c - 1];
	}
	if (c < 3)
	{
		maps[r][c + 1] = !maps[r][c + 1];
	}
	maps[r][c] = !maps[r][c];
}

void Solution(int index,bool maps[4][4],int count,int &min)
{
	if (index == 16)
	{
		if (Check(maps)&&min > count )
		{
			min = count;
		}
		return;
	}
	bool temp[4][4];
	memset(temp, true, 16);
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			temp[i][j] = maps[i][j];
		}
	}
	Solution(index + 1, temp,count,min);
	Flip(index, temp);
	Solution(index + 1, temp,count+1,min);
}

int main()
{
	char map[4][5];
	bool maps[4][4];
	memset(maps, true, 16);
	char n;
	while (~scanf("%20c", map,map+1,map+2,map+3, map + 4, map + 5, map + 6, map + 7, map + 8, map + 9, map + 10, map + 11, map + 12, map + 13, map + 14, map + 15,map+16,map+17,map+18,map+19 ))
	{
		int count = 0;
		int min = 17;
		bool flag = true;
		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < 4; j++)
			{
				if (map[i][j] != map[0][0])
				{
					flag = false;
				}
				if (map[i][j] == 'w')
				{
					maps[i][j] = true;
				}
				else
				{
					maps[i][j] = false;
				}
			}
		}
		Solution(0, maps, count, min);
		if (min == 17)
		{
			cout << "Impossible" << endl;
		}
		else if (!flag)
		{
			Solution(0, maps, count, min);
			cout << min<<endl;
		}
		else
		{
			cout << "0"<<endl;
		}
	}
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator