搜素题 --java

Poj2531

首先把所有节点都放在一组，然后采用深度优先搜索的方法，对每一个节点都做判断是否应该移到另一组去，判断的依据是移过去和不移过去哪个得到的和值比较大（这里移去B组后的计算方法就是加上该点和在A组中的所有点的间距，和减去原本就在B组中的所有点的间距），如果移过去变小了，那么则不移过去，并剪掉该条支路。

 

import java.util.*;

public class Main1 {
     static int ans=0;
     static int map[][];
     static boolean vis[]=new boolean[10010];
     public static  void dfs(int id,int n,int sum){
         vis[id]=true;
         int tem=sum;
         for(int i=0;i<n;i++){
             if(vis[i])
                 tem-=map[id][i];
             else
                 tem+=map[id][i];
         }
         if(tem>ans)
             ans=tem;
         if(tem>sum){
             for(int i=id+1;i<n;i++)
                 dfs(i, n, tem);
         }
         vis[id]=false;
     }
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int n =sc.nextInt();
         map=new int [n][n];
         for(int i=0;i<n;i++)
             for(int j=0;j<n;j++)
             map[i][j]=sc.nextInt();
         dfs(0,n,0);
         System.out.println(ans);
    }

}

poj3278

 题意： FJ要抓奶牛。 开始输入N（FJ的位置）K（奶牛的位置）。
*            FJ有三种移动方法： 1、向前走一步，耗时一分钟。
*            2、向后走一步，耗时一分钟。 3、向前移动到当前位置的两倍N*2，耗时一分钟。
*            问FJ抓到奶牛的最少时间。PS：奶牛是不会动的。
 

 

import java.util.*;

public class Main1{
    static int ans = 0;
    static int map[][];
    static boolean vis[] = new boolean[10010];
    static int step[] = new int[10010];
    static Queue<Integer> q = new LinkedList<Integer>();

    public static int bfs(int n, int k) {
        int head, next;
        while (!q.isEmpty())
            q.clear();
        q.offer(n);
        vis[n] = true;
        step[n] = 0;
        while (!q.isEmpty()) {
            head = q.poll();
            for (int i = 0; i < 3; i++) {
                if (i == 0)
                    next = head + 1;
                else if (i == 1)
                    next = head - 1;
                else
                    next = 2 * head;
                if (next < 0 || next > 10010)
                    continue;
                if (!vis[next]) {
                    step[next] = step[head] + 1;
                    q.offer(next);
                    vis[next] = true;
                }
                if (next == k)
                    return step[k];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        if (n >= k)
            System.out.println(n - k);
        else {
            int ans = bfs(n, k);

            System.out.println(ans);
        }
    }
}