ただの適当な開発記

会社勤めしつつUnityでアプリ作ってる人の雑記

AOJ-0071: Bombs Chain

蟻本でアルゴリズムの勉強してます。
再帰関数を使った深さ優先探索がやっとわかってきました。
蟻本に乗ってる水たまりの問題を参考にしました。

import java.util.*;
public class AOJ0071 {
	public static char[][] map = new char[8][8];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int max_roop = sc.nextInt();
		int playcount =1;
		while(max_roop>=playcount){ 
			for(int i = 0;i < 8;i++){
				String tmp = sc.next();
				for(int j = 0;j < 8;j++){
					map[i][j] = tmp.charAt(j);
				}
			}
			int m = sc.nextInt();
			m--;
			int n = sc.nextInt();
			n--;
			dfs(n,m);
			System.out.println("Data "+playcount+":");
			for(int i = 0; i <8;i++){
				for(int j= 0;j < 8;j++){
					System.out.print(map[i][j]);
				}
				System.out.println();
			}
			playcount++;
		}
	}
	public static void dfs(int x,int y){
		map[x][y]='0';
		for(int dx = -3;dx <=3;dx++){
			for(int dy = -3; dy <= 3 ; dy++){
				if(dx == 0 || dy ==0){
					int nx = x + dx;
					int ny = y + dy;
					if(0<=nx&&nx<8&&0<=ny&&ny<8&&map[nx][ny]=='1')dfs(nx,ny);
				}
			}
		}
		return;
	}
}

汚いコードですみません。
標準入力の部分が点在してるとどうしても汚く見えてしまう気がします。気を配らないと。


・反省点

  • dfs内の条件if(dx == 0 || dy ==0)を最初書いていなかったために判定の範囲が6*6四方になってしまいました。
  • 次へ進む条件のmap[nx][ny]=='1'も何故か最初map[x][y]=='0'としてしまい進まない
  • char型の配列なのに条件内で==nとしていたためメソッド動かず

くらいですかね。バグ取りに多く時間とられちゃいました。この問題はICPC本番だとどのくらいの難易度なんですかね。
B~Cの間とかだと嬉しいけど、Aとかなんだろうなぁ。。

会社の研修だと規約にのっとった見やすいコードを書くように強く言われてるんですが、まあそうはいきませんよね。。

次は幅優先探索を見ていきます。このペースじゃ本番までに蟻本初級編を終えられたらいい方かなー。

広告を非表示にする