搜素题 --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);

        }

    }

}