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

自己想的算法(不知道该叫啥),小错误改完之后,0ms AC!感兴趣的可以瞅瞅!(附几组测试数据)

Posted by 771385494 at 2012-03-29 19:15:05 on Problem 1315
#include <iostream>
#include <set>
using namespace std;

multiset<int> s;
multiset<int>::iterator pos;
int n;

int Init(char a[][5],int h,int l)
{
	int i,count = 0;
	for(i = l + 1;i < n;i++)//行
		if(a[h][i] == 'X')
			break;
		else
			count++;
	for(i = l - 1;i >= 0;i--)//行
		if(a[h][i] == 'X')
			break;
		else
			count++;
	for(i = h + 1;i < n;i++)//列
		if(a[i][l] == 'X')
			break;
		else
			count++;
	for(i = h - 1;i >= 0;i--)//列
		if(a[i][l] == 'X')
			break;
		else
			count++;
	return count;			
}
bool Set(char a[][5],int h,int l)
{
	int i;
	multiset<int>::iterator pos1;

	for(i = l;i < n;i++)//行
		if(a[h][i] == 'X')
			break;
		else{
			pos1 = s.find(a[h][i] - '0');
			if(pos1 != s.end())
				s.erase(pos1);
			a[h][i] = ' ';
		}
	
	for(i = l - 1;i >= 0;i--)//行
		if(a[h][i] == 'X')
			break;
		else {
			pos1 = s.find(a[h][i] - '0');
			if(pos1 != s.end())
				s.erase(pos1);
			a[h][i] = ' ';
		}
	for(i = h;i < n;i++)//列
		if(a[i][l] == 'X')
			break;
		else {
			pos1 = s.find(a[i][l] - '0');
			if(pos1 != s.end())
				s.erase(pos1);
			a[i][l] = ' ';
		}
	for(i = h - 1;i >= 0;i--)//列
		if(a[i][l] == 'X')
			break;
		else {
			pos1 = s.find(a[i][l] - '0');
			if(pos1 != s.end())
				s.erase(pos1);
			a[i][l] = ' ';
		}
	
	return true;
}
int main()
{
	int i,j,k = 0,count = 0,result = 0;
	char map[4][5];
	while(cin >> n && n != 0) {
		for(i = 0;i < n;i++)
			cin >> map[i];
		for(i = 0;i < n;i++)
			for(j = 0;j < n;j++) {
				if(map[i][j] != 'X') {
					count = Init(map,i,j);
					s.insert(count);
					map[i][j] = count + '0';
				}
			}
		while(!s.empty()) {
			bool set = false;
			pos = s.begin();
			int tmp = *pos;
			for(i = 0;i < n;i++) {
				for(j = 0;j < n;j++) {
					if(map[i][j] == 'X')
						continue;
					if(tmp == map[i][j] - '0') {
						set = Set(map,i,j);
						result++;
						break;
					}
				}
				if(set)
					break;
			}
		}
		cout << result << endl;
		result = 0;
		s.clear();
	}
	return 0;
}

4
..X.
.X.X
..X.
.X..
7

1
X
0

1
.
1

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