poj 1414 DP

網上搜的分類是DP，但是周遊就行了。。。。隻不過有點麻煩。。。。。

AC代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 0x3f3f3f3f

struct Point{
	int x, y;
};

struct Group{
	int id;
	int size;
	Point p[55];
	int cnt;
};

int num[11][11], N, C, groupnum;
Group group[55];
bool mark[11][11];
int hashs[11][11];
int moves[][2] = { { 0, 1 }, { 0, -1 }, { -1, -1 }, { -1, 0 }, { 1, 0 }, { 1, 1 } };

void DFS( int x, int y, int groupid, queue<Point> &q ){
	if( x > N || x < 1 || y > N || y < 1 || y > x || mark[x][y] ){
		return;
	}
	if( num[x][y] != group[groupid].id ){
		return;
	}
	Point pp;
	pp.x = x;
	pp.y = y;
	q.push( pp );
	mark[pp.x][pp.y] = true;
	for( int i = 0; i < 6; i++ ){
		DFS( x + moves[i][0], y + moves[i][1], groupid, q );
	}
}

int main(){
	
	while( cin >> N >> C && !( N == 0 && C == 0 ) ){
		
		groupnum = 0;
		
		//讀資料
		for( int i = 1; i <= N; i++ ){
			for( int j = 1; j <= i; j++ ){
				scanf( "%d", &num[i][j] );
			}
		}
		
		//分組
		memset( mark, false, sizeof( mark ) );
		for( int i = 1; i <= N; i++ ){
			for( int j = 1; j <= i; j++ ){
				if( num[i][j] != 0 && !mark[i][j] ){
					
					group[groupnum].id = num[i][j];
					int cnt = 0;
					
					queue<Point> q;
					while( !q.empty() ){
						q.pop();
					}
					DFS( i, j, groupnum, q );//深搜搜出相連的為一組
					
					group[groupnum].size = q.size();

					//找出與該組相連的空位
					bool tempmark[130];
					memset( tempmark, false, sizeof( tempmark ) );
					while( !q.empty() ){
						Point p = q.front();
						q.pop();
						hashs[p.x][p.y] = groupnum;
						for( int k = 0; k < 6; k++ ){
							Point temppoint = p;
							temppoint.x += moves[k][0];
							temppoint.y += moves[k][1];
							if( temppoint.x > N || temppoint.x < 1 || temppoint.y > N || temppoint.y < 1 || temppoint.y > temppoint.x ){
								continue;
							}
							if( num[temppoint.x][temppoint.y] != 0 || tempmark[temppoint.x*11+temppoint.y] ){
								continue;
							}
							group[groupnum].p[cnt].x = temppoint.x;
							group[groupnum].p[cnt++].y = temppoint.y;
							tempmark[temppoint.x*11+temppoint.y] = true;
						}
					}

					group[groupnum++].cnt = cnt;
				}
			}

		}

		//周遊
		int ans = -MAX;
		for( int i = 1; i <= N; i++ ){
			for( int j = 1; j <= i; j++ ){
				
				if( num[i][j] != 0 ){
					continue;
				}
				
				int sub = 1, add = 0;
				//計算能消的
				for( int k = 0; k < groupnum; k++ ){
					if( group[k].cnt > 1 ){
						continue;
					}else{
						if( group[k].p[0].x == i && group[k].p[0].y == j ){
							if( group[k].id == C ){
								sub += group[k].size;
							}else{
								add += group[k].size;
							}
						}
					}
				}

				//計算自己要被消的數量
				int flag = 1;
				for( int k = 0; k < 6; k++ ){
					int tempx = i, tempy = j;
					tempx += moves[k][0];
					tempy += moves[k][1];
					if( tempx > N || tempx < 1 || tempy > N || tempy < 1 || tempy > tempx ){
						continue;
					}
					if( num[tempx][tempy] == 0 ){
						flag = 0;
						break;
					}
					if( num[tempx][tempy] == C && group[hashs[tempx][tempy]].cnt > 1 ){
						flag = 0;
						break;
					}
				}
				if( !flag ){
					sub = 0;
				}
				
				//取最大
				ans = max( ans, add - sub );
			}
		}

		cout << ans << endl;
	}

	return 0;
}