好贷网好贷款

Topcoder srm 590 dv2 500分题目

发布时间:2016-12-5 10:26:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Topcoder srm 590 dv2 500分题目",主要涉及到Topcoder srm 590 dv2 500分题目方面的内容,对于Topcoder srm 590 dv2 500分题目感兴趣的同学可以参考一下。

转载请注明来自souldak,微博:@evagle 昨天晚上做了第一场topcoder比赛,不知道是70分钟就结束了,结果只交了第一题,第二题没来的及。但是第二题的其实还是很简单的,数据范围也很小。直接暴力搜索就OK。 题目是要求放一颗黑棋子,求出最多能围死多少白棋子,被围死就是白棋子周围没有空格了。其实和我上一篇leetcode Surrounded Regions 详解很相似。首先对于每一个empty的cell,假设在这里放一个棋子,计算会有多少被围死的,然后取其中最大的。现在就是考虑给一个棋盘,如何得到被围死的棋子数,也就回到了surronded regions。BFS遍历所有的连在一起的白棋子,如果其中有一个是挨着empty cell的,就说明没有被围死的,否则说明这个已经被围死了,返回这次bfs到的白棋子数目。然后将每一堆被围死的数目相加即可。 package srm590; import java.awt.Point; import java.util.LinkedList; import java.util.Queue; public class SRM590DV1s500 { //x for black //o for white //. for empty class Point{ int x; int y; Point(int x,int y){this.x=x;this.y=y;} Point(){}; } boolean expand(String[] board,int[][] visit,Queue<Point> queue, int x, int y,int row,int col){ if(x<0||x>=row||y<0||y>=col) return false; else{ if(visit[x][y]==0){ visit[x][y] = 1; if(board[x].charAt(y)=='o'){ queue.add(new Point(x,y)); return false; }else if(board[x].charAt(y)=='.'){ return true; }else return false; } return false; } } int bfs(String[] board,int[][] visit, int x, int y,int row,int col){ int count=0; boolean reachEmpty=false; Queue<Point> queue = new LinkedList<Point>(); queue.add(new Point(x,y)); while(!queue.isEmpty()){ Point p = queue.poll(); visit[p.x][p.y]=2; count++; reachEmpty |= expand(board,visit,queue,p.x-1,p.y,row,col); reachEmpty |= expand(board,visit,queue,p.x+1,p.y,row,col); reachEmpty |= expand(board,visit,queue,p.x,p.y-1,row,col); reachEmpty |= expand(board,visit,queue,p.x,p.y+1,row,col); } if(reachEmpty) return 0; else return count; } int getKilled(String[] board,int row,int col){ int count=0; int[][] visit = new int[20][20]; for(int i=0;i<20;i++) for(int j=0;j<20;j++) visit[i][j] = 0; for(int r=0;r<board.length;r++){ for(int c=0;c<board[0].length();c++){ if(board[r].charAt(c)=='o'&&visit[r][c]==0){ count += bfs (board,visit,r,c,row,col); } } } return count; } public int maxKill(String[] board) { int max = 0; int row = board.length; int col = board[0].length(); for(int r=0;r<row;r++){ for(int c=0;c<col;c++){ if(board[r].charAt(c)=='.'){ String tmp = board[r]; if(c<col-1) board[r] = tmp.substring(0,c)+'x'+tmp.substring(c+1); else board[r] = tmp.substring(0,c)+'x'; int count = getKilled(board, row, col); if(max<count) max = count; board[r] = tmp; } } } return max; } public static void main(String[] args) { String[] board ={".xoxo", "ooxox", "oooxx", "xoxox", "oxoox"}; SRM590DV1s500 srm = new SRM590DV1s500(); System.out.println(srm.maxKill(board)); } }

上一篇:内存管理二
下一篇:inline函数和宏的区别

相关文章

相关评论