Topcoder srm 590 dv2 500分题目
转载请注明来自souldak，微博:@evagle
昨天晚上做了第一场topcoder比赛，不知道是70分钟就结束了，结果只交了第一题，第二题没来的及。但是第二题的其实还是很简单的，数据范围也很小。直接暴力搜索就OK。
题目是要求放一颗黑棋子，求出最多能围死多少白棋子，被围死就是白棋子周围没有空格了。其实和我上一篇package srm590;import java.awt.Point;import java.util.LinkedList;import java.util.Queue;public class SRM590DV1s500 {//x for black//o for white//. for emptyclass 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;}elsereturn 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);elseboard[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));}}
