Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
深搜,深搜,深搜,此题略冷,源码留念#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef pair<int , int> P; int field[11][11]; bool check[11][11]; vector<P> empty_arr; int dx[] = {-1,1,0,1,-1, 0}; int dy[] = { 0,0,1,1,-1,-1}; int N, T; void dfs(int x, int y, int tar){ check[x][y] = true; for (int i = 0; i < 6; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && ny >= 0 && ny <= nx && nx < N){ if (field[nx][ny] == tar && !check[nx][ny]){ dfs(nx, ny, tar); } } } } int main(){ while (~scanf("%d %d", &N, &T)){ if (N == 0 && T == 0){ break; } empty_arr.clear(); for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { scanf("%d", &field[i][j]); if (field[i][j] == 0){ empty_arr.push_back(P(i,j)); } } } int ans = -1 * 0x3f3f3f3f; for (int k = 0; k < empty_arr.size(); ++k) { field[empty_arr[k].first][empty_arr[k].second] = T; memset(check, 0, sizeof(check)); for (int j = 0; j < empty_arr.size(); ++j) { if (j == k){ continue; } for (int i = 0; i < 6; ++i) { int nx = empty_arr[j].first + dx[i]; int ny = empty_arr[j].second + dy[i]; if (nx >= 0 && ny >= 0 && ny <= nx && nx < N){ if (field[nx][ny] != 0 && !check[nx][ny]){ dfs(nx, ny, field[nx][ny]); } } } } int res = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { if (!check[i][j] && field[i][j] != 0){ if (field[i][j] != T){ res ++; } else { res --; } } } } ans = max(res, ans); field[empty_arr[k].first][empty_arr[k].second] = 0; } printf("%d\n", ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator