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

深搜,深搜,深搜,此题略冷,源码留念

Posted by vjubge4 at 2019-04-09 09:09:20 on Problem 1414
#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:
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