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

感动!~首次一次AC,暴力,差一点超时

Posted by zzayxh at 2019-01-17 19:04:53 on Problem 2965
#include<iostream>
#include<algorithm>
using namespace std;
char a[5][5];
int open;
int flag[20];

void change(int i, int j) {
	for (int k = 0; k < 4; k++)
	{
		if (a[i][k] == '-')
		{
			a[i][k] = '+';
			open--;
		}
		else
		{
			a[i][k] = '-';
			open++;
		}
	}
	for (int k = 0; k < 4; k++)
	{
		if (k==i)
		{
			continue;
		}
		if (a[k][j] == '-')
		{
			a[k][j] = '+';
			open--;
		}
		else
		{
			a[k][j] = '-';
			open++;
		}
	}

}

int solve(int times, int x) {
	if (open==16)
	{
		return times;
	}
	if (x == 16)
	{
		return 17;
	}
	int i = x / 4;
	int j = x % 4;
	change(i, j);
	int minn = solve(times + 1, x + 1);
	change(i, j);
	int t = solve(times, x + 1);
	if (minn >t)
	{
		minn = t;
		flag[x] = 0;
	}
	else if (t > minn)
	{
		flag[x] = 1;
	}
	return minn;
}

int main() {
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			cin >> a[i][j];
			if (a[i][j]=='-')
			{
				open++;
			}
		}
	}
	if (open==16)
	{
		cout << 0;
	}
	else
	{
		cout << solve(0, 0) << endl;
		 for (int i = 0; i < 16; i++)
		 {
			 if (flag[i]==1)
			 {
				 cout << i / 4 + 1 << ' ' << i % 4 + 1 << endl;
			 }
		 }
	}
	system("pause");
	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