AOJとは
AOJ とういうのは，AIZU ONLINE JUDGE という会津大学運営しているプログラミングのオンラインジャッジシステムです．
プロコン (プログラミングコンテスト) にて出題された問題などがリストアップされてます．
調べればいくらでもこういう系のジャッジシステムや，ゲームや，アプリがある世の中になってきているので，自分のプログラムスキルを調べたい！あげたい！って人にはいいですね．
Check io とか CodeIQ とか Learn Python とか…
AOJ0118
問題はここに
深さ優先探索の問題です．
ざっくりいうと
最初に 10 10 など，スペースで区切られた数字 (果樹園の大きさ) が与えられるので，
となりあってる @ or # or * は 1 この塊だと数えて，何個に分けられるか．
って問題です．
例えばこんな感じ (コピペでごめんなさい)
こんな感じの【 2 この数字と@ or # or * 】が与えられて，区切ると 4 つなので 4 と出力する．
なぜ 4 になるか．ですが，上の例だと，
- 左上の 2 つの #
- 右の 3 つの @
- 真ん中の 3 つの *
- 左下の #
これが塊なので 4 ですね．
最後に 0 0 が入力されたら終了．
詳しくは問題見てください．
ローカル環境だと動くんですけどねぇ…
ってるんだよなー．
と思ってたら，このブログを書いてる間に自己解決しました，しょぼミスでした．
縦と横逆にしてました（笑）
3 * 3 とか 5 * 5 とかの正方形だとうまくいきますが， 3 * 5 とか与えられたときに死んでたんですね．万事解決．
コード (修正済み)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | # -*- coding:utf-8 -*- import sys def dfs(x, y, sym): tile[x][y] = "." for i in range(len(DX)): nx = x + DX[i] ny = y + DY[i] if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym): dfs(nx, ny, sym) def solve(): res = 0 for i in range(N): for j in range(M): sym = tile[i][j] if tile[i][j] != ".": if tile[i][j] is sym: dfs(i, j, sym) res += 1 print(res) counter=0 DX = [-1,0,1,0] DY = [0,-1,0,1] sys.setrecursionlimit(10**7) while True: line = input() if " " in line: nums = line.split(" ") N = int(nums[0]) M = int(nums[1]) tile = [[0 for i in range(M)] for j in range(N)] else: tile[counter-1] = list(line) if N is 0 and M is 0: break counter += 1 if counter-1 is N: solve() counter = 0 |
