蓝桥杯 历届试题 剪格子(dfs搜索) - Freecode# - 博客园


蓝桥杯 历届试题 剪格子(dfs搜索) - Freecode# - 博客园
如下图所示,3 x 3 的格子中填写了一些整数。
+--*--+--+
|10* 1|52|
+--****--+
|20|30* 1|
*******--+
| 1| 2| 3|
+--+--+--+
我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是60。
本题的要求就是请你编程判定:对给定的m x n 的格子中的整数,是否可以分割为两个部分,使得这两个区域的数字和相等。
如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割,则输出 0。
输入格式
程序先读入两个整数 m n 用空格分割 (m,n<10)。
表示表格的宽度和高度。
接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000。
输出格式
输出一个整数,表示在所有解中,包含左上角的分割区可能包含的最小的格子数目。
样例输入1
3 3
10 1 52
20 30 1
1 2 3
样例输出1
3
样例输入2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例输出2
10

  
  dfs搜索题。
  按深度优先搜索的思路从左上角开始搜索,累加当前数字,直到数字和为所有数字和的一半,返回走到当前的步数。
  需要注意的是,输入行数和列数的时候注意输入顺序。我之前做过的这种类型的题,都是先输入行数再输入列数,而这道题却是先输入列数再输入行数。这着实坑到我了,调了好久才找到原因。
http://www.zhuangjingyang.com/%E5%89%AA%E6%A0%BC%E5%AD%90.html
public class Main
{
 private static int m = 0; //col
 private static int n = 0; //row
 private static int half = 0;
 private static int sum = 0;
 private static int minValue = 100;
 private static int count = 0;
 private static int select = 0;
 private static int tnum;
 
 private static int [][] num = new int[10][10];
 private static int [][] flag = new int[10][10];
 

 private static int xzb[] = {-1,1,0,0};//上下左右
 private static int yzb[] = {0,0,-1,1};

 
 public static void main(String[] args)
 {
  int i,j,maxNum = 0, all =0;
  Scanner cin = new Scanner(System.in);
  m = cin.nextInt();
  n = cin.nextInt();
  
  for(i=0;i<n; ++i)
   for(j=0;j<m;j++)
   {
    num[i][j] = cin.nextInt();
    all += num[i][j]; //all为总和
    
    if(num[i][j] > maxNum) //找出最大值
     maxNum = num[i][j];
   }
  
  if(all%2!=0 || maxNum > all/2) //如果为奇数或者最大值大于总和一半,则没有结果
   System.out.println("0");
  else
  {
   half = all /2 ;
   //将格子每个点都作为起点搜索一遍,两个 for 循环
   for(i=0;i<m;i++)
   {
    for(j=0;j<n;j++)
    {
     select = 0;
     dfs(num[i][j],i,j);
    }
   }
   
   if(minValue != 100) //结果
    System.out.print(minValue);
   else
    System.out.print("0");
  }
  
 }
 
 static int isok(int x,int y) //判断传入的坐标值是否能被选入
 {
  int yes = 0; //不越界并且不超出和一半
  if((x>=n || x<0) || (y>=m||y<0)||(flag[x][y] == 1)||(sum+num[x][y] > half))
   yes = 1; // 冲突
  return yes;
 }
 
 
 static void back(int value,int x,int y)//执行回退处理
 {
  if(x==0 && y==0) //如果将 num[0][0] 回退掉,则标记为未选入
   select = 0; 
  -- count ;
  sum -= value;
  flag[x][y] = 0;
 }
 
 
 static void  dfs(int value,int x,int y) //dfs搜索
 {
  int i, t1, t2;
  
  if(x==0 && y==0) //主要用于B点开始的搜素,判断num[0][0]有没有被选入
   select = 1;
  flag[x][y] = 1; //标记为走过
  ++count;
  sum += value;
  
  if( sum == half)
  {
   if(select == 1) /*如果num[0,0]被选入,主要用于非[0,0]点开始的搜索*/
    tnum = count;
   
   else
    tnum = n*m - count;
   
   if(minValue > tnum)
    minValue = tnum;
  }
  else
  {
   for(i=0;i<4;i++)/*按 上下左右 顺序遍历*/
   {
    t1 = x + xzb[i];/*引入t1,t2目的是使传入的x,y值不变,便于下面的回退*/
    t2 = y + yzb[i];
    if(isok(t1,t2) == 1) //判断是否可走
     continue;
    dfs(num[t1][t2],t1,t2);
   }
  }
  //如果都不可以走,则回退
  back(value,x,y); 
 }
}
http://blog.csdn.net/acmman/article/details/18659573
int num[15][15],visit[15][15]; int i,j,n,m,sum,end=0; void Cutaws(int x,int y,int value,int count) { value+=num[x][y]; if(value==sum/2&&end!=1) { printf("%d\n",count+1); memset(visit,1,sizeof(visit)); end=1; return; } if(value>sum) return; if(y+1<n&&visit[x][y+1]==0) { visit[x][y+1]=1; Cutaws(x,y+1,value,count+1); visit[x][y+1]=0; } if(y-1>=0&&visit[x][y-1]==0) { visit[x][y-1]=1; Cutaws(x,y-1,value,count+1); visit[x][y-1]=0; } if(x+1<m&&visit[x+1][y]==0) { visit[x+1][y]=1; Cutaws(x+1,y,value,count+1); visit[x+1][y]=0; } if(y-1>=0&&visit[x-1][y]==0) { visit[x-1][y]=1; Cutaws(x,y,value,count+1); visit[x-1][y]=0; } } int main() { sum=0; memset(num,0,sizeof(num)); memset(visit,0,sizeof(visit)); scanf("%d%d",&n,&m); for(i=0;i<m;i++) for(j=0;j<n;j++) { scanf("%d",&num[i][j]); sum+=num[i][j]; } visit[0][0]=1; Cutaws(0,0,0,0); return 0; }
Read full article from 蓝桥杯 历届试题 剪格子(dfs搜索) - Freecode# - 博客园

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts