C言語関係掲示板

過去ログ

No870 n×nの配列で#を陸、+を水として書いた地図の変換

[戻る] [ホームページ]
No.11283

2次元配列の変換プログラム
投稿者---kaz(2003/12/18 14:17:59)


n×nの配列で#を陸、+を水として書いた地図の、配列の外側を海とし海からの縦、横の水を-として変換プログラムを考えているのですがわかりません。どなたか教えてもらえませんか?
例えば
+++#+++
++####+
+##+#+#
+#++#++
++###++
####+##
++#++++
を変換して
---#---
--####-
-##+#-#
-#++#--
--###--
####-##
--#----
となるようにしたいのですが・・・

No.11286

Re:2次元配列の変換プログラム
投稿者---かずま(2003/12/18 14:54:41)


> n×nの配列で#を陸、+を水として書いた地図の、配列の外側を海とし海から
> の縦、横の水を-として変換プログラムを考えているのですがわかりません。

1. 一番外側の四角の + を無条件に - に変える。
2. ひとつ内側の四角の + は、上下左右のどこかに - があれば - に変える。
3. 中心になるまで 2 を繰り返す。

このアルゴリズムでいかがでしょうか?
プログラムが書けたら報告してくださいね。

No.11289

Re:2次元配列の変換プログラム
投稿者---たいちう(2003/12/18 16:15:55)


> このアルゴリズムでいかがでしょうか?

++++++...
+#####...
+#++#+...
+##+#+...
++++#+...
.........
.........

例えば左上がこんな場合駄目でしょ。
一番外側の全ての+を起点として、再帰で処理するのが定石かと。

No.11298

Re:2次元配列の変換プログラム
投稿者---かずま(2003/12/18 20:51:22)


> 例えば左上がこんな場合駄目でしょ。

そうですね。問題を見てすぐに思いついた解法だったんですが、
考えが足りませんでした。

No.11306

Re:2次元配列の変換プログラム
投稿者---かずま(2003/12/19 02:26:50)


> 一番外側の全ての+を起点として、再帰で処理するのが定石かと。

これに従ってプログラムを書いてみると、
#include <stdio.h>

#define N  100

char a[N][N];  unsigned int n;

void try(unsigned int i, unsigned int j)
{
    if (i < n && j < n && a[i][j] == '+')
        a[i][j] = '-', try(i-1,j), try(i+1,j), try(i,j-1), try(i,j+1);
}

int main(void)
{
    unsigned int i, j;

    if (scanf("%u", &n) != 1 && n > N) return 1;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (scanf(" %c", &a[i][j]) != 1) return 1;
    
    for (i = 0; i < n; i++)
        try(0, i), try(n-1, i), try(i, 0), try(i, n-1);
    
    printf("%u\n", n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            putchar(a[i][j]);
        putchar('\n');
    }
    return 0;
}


No.11309

Re:2次元配列の変換プログラム
投稿者---たいちう(2003/12/19 09:37:53)


> void try(unsigned int i, unsigned int j)
> {
>     if (i < n && j < n && a[i][j] == '+')
>         a[i][j] = '-', try(i-1,j), try(i+1,j), try(i,j-1), try(i,j+1);
> }

ちょっと見たところ、i, j が負になりませんか?



No.11310

Re:2次元配列の変換プログラム
投稿者---たいちう(2003/12/19 09:39:36)


unsigned int でしたね。
失礼しました。

No.11340

Re:2次元配列の変換プログラム
投稿者---かずま(2003/12/20 12:48:33)


>   if (scanf("%u", &n) != 1 && n > N) return 1;

訂正です。
    if (scanf("%u", &n) != 1 || n > N) return 1;