冀教网 - 河北教师网站 - 专注于冀教版课本资源

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 61|回复: 0

P1123 取数游戏

[复制链接]

3万

主题

3万

帖子

11万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
118556
发表于 2020-5-24 01:22 | 显示全部楼层 |阅读模式
题目描述

一个N×M的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻88个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
输入格式

第1行有一个正整数T,表示了有T组数据。
对于每一组数据,第一行有两个正整数N和M,表示了数字矩阵为N行M列。
接下来N行,每行M个非负整数,描述了这个数字矩阵。
输出格式

T行,每行一个非负整数,输出所求得的答案。
我的关键词 P1123 取数游戏  新闻资讯 1685879-20200524004923606-336848476


说明/提示

对于第1组数据,取数方式如下:
[67] 75 63 10
29 29 [92] 14
[21] 68 71 56
8 67 [91] 25
====>>洛谷

————————————————————分隔线————————————————————————————————————
对于这种题目,如果要求不高的话,要求最大值,一般都可以用DFS算法,枚举各种可能的值,然后比较即可得出结果。这道题有点棘手的地方在于,一个数,要标记其是否已被访问,因为是八方向,情况似乎有多种,用Boolean来记录的话, 貌似不太可行。我们可以用一个int类型的变量来记录,当这个数被访问时,该变量自增,当回溯时,该变量自减==>所以当该变量为零时,该数未被访问。当遇到一个数时,有取与不取两种选择,这两种选择我们都应该尝试一遍。
源代码:
  1. import java.util.Scanner;public class Main {    static int T, N, M, Max;    static int[][] nums = new int[10][10];    static int[][] visited = new int[10][10];
  2.     //左上,上, 右上,左,右,左下,下,右下    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        T = sc.nextInt();        for(int i = 0; i < T; i++) {            N = sc.nextInt();            M = sc.nextInt();            for(int r = 0; r < N; r++) {                for(int c = 0; c < M; c++) {                    nums[r][c] = sc.nextInt();                    visited[r][c] = 0;                }            }            Max = 0;            DFS(0, 0, 0);            System.out.println(Max);                 }    }        public static void DFS(int x, int y, int sum) {        if(y >= M) {            y = 0;            x = x + 1;            if(x >= N) {                Max = Max > sum ? Max : sum;                return;            }        }        DFS(x, y+1, sum);  //不取该数
  3.      //取该数        if(visited[x][y] == 0) {            for(int i = 0; i < 8; i++) {                if(x+dx[i] >= 0 && y+dy[i] >= 0)                visited[x+dx[i]][y+dy[i]]++;            }            DFS(x, y+1, sum+nums[x][y]);            for(int i = 0; i < 8; i++) {                if(x+dx[i] >= 0 && y+dy[i] >= 0)                visited[x+dx[i]][y+dy[i]]--;            }        }    }}
复制代码


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|冀教网 - 河北教师网站 - 专注于冀教版课本资源  

GMT+8, 2020-5-27 13:03 , Processed in 0.288999 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表