汉密尔顿路径

Java 解法, 执行用时: 66ms, 内存消耗: 11832K, 提交时间: 2023-04-16 16:31:57

import java.util.*;

/**
 * description:
 * 汉密尔顿路径
 * @author czs
 * @create 2023-04-16 14:36
 */
public class Main {
static int n;
    static char[][] map;
    static boolean[] visited;
    static int[] res;
    static int[] out;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = Integer.parseInt(in.nextLine());
        map = new char[n][n];
        out = new int[n+1];
        for (int i = 0; i < n; i++) {
           map[i] = in.nextLine().toCharArray();
            for (int j = 0; j < n; j++) {
                if(map[i][j] == '+') out[i]++;
            }
        }
        visited = new boolean[n];
        res = new int[n];
        int maxIndex = n;
        out[maxIndex] = -1;
        for (int i = 0; i < n; i++) {
            maxIndex = findMax(maxIndex);
            visited[maxIndex] = true;
            res[i] = maxIndex;
            for (int j = 0; j < n; j++) {
                if(map[j][maxIndex] == '+') out[j]--;
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.print(res[i]);
            if(i!=n-1){
                System.out.print(" ");
            }
        }
        in.close();
    }

    private static int findMax(int k) {
        int maxOut = -1;
        int maxIndex = -1;
        for (int i = 0; i < n; i++) {
            if( (k==n || map[k][i] == '+') && out[i]>maxOut && !visited[i]){
                maxOut = out[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 488K, 提交时间: 2019-12-31 17:40:25

#include<bits/stdc++.h>
using namespace std;
const int N=105;
char mp[N][N];
int main() {
    int n;scanf("%d",&n);
    for(int i=0; i<n; ++i)scanf("%s",mp[i]);
    list<int> path;
    for(int i=0; i<n; ++i) {
        auto it=path.begin();
        while(it!=path.end())
            if(mp[i][*it]=='+')break;
            else ++it;
        path.insert(it,i);
    }
    for(int x:path)printf("%d ",x);
    return 0;
}

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 508K, 提交时间: 2021-03-01 22:17:38

#include<bits/stdc++.h>
using namespace std;
const int N=105;
char mp[N][N];
int main() {
    int n;scanf("%d",&n);
    for(int i=0; i<n; ++i)scanf("%s",mp[i]);
    list<int> path;
    for(int i=0; i<n; ++i) {
        auto it=path.begin();
        while(it!=path.end())
            if(mp[i][*it]=='+')break;
            else ++it;
        path.insert(it,i);
    }
    for(int x:path)printf("%d ",x);
    return 0;
}

详情