Pemetaan Area (Mapping) Sederhana Dengan C/C++

Posted on Updated on

Total War

Pemetaan wilayah (mapping) merupakan salah satu aplikasi yang banyak digunakan dalam kehidupan sehari-hari. Mapping bisa diimplementasikan dengan menggunakan sebuah program yang otomatis akan memberitahukan data-data dari area. Implementasi mapping bisa dilakukan menggunakan berbagai bahasa pemrograman. Tapi kali ini, kita akan belajar sebuah mapping yang sederhana. Mungkin ini belum bisa disebut dengan map, tapi cukup memberi ilustrasi tentang map itu sendiri. Bahasa yang digunakan adalah bahasa C/C++. Hehe, tampilannya masih console, belum GUI.

Di sini kita akan membuat sebuah simulasi area perang. Diberikan informasi tentang petak-petak dimensi area peta yang ada. Kemudian pemberian informasi tentang area-area perang yang ada. Nantinya program akan memberitahukan jumlah area secara otomatis.

Mungkin temen-temen masih banyak yang bingung. Kita masuk ke ilustrasi saja. Diberikan gambar sebagai berikut :

peta

Area merah merupakan area-area yang sedang terjadi perang. Area hijau, orange, dan abu-abu merupakan area dari pengaruh kekuasaan yang ada. Dan setelah area dipetakan, program akan secara otomatis menghitung berapa banyak area perang yang terjadi. Perhitungan dilakukan pada area merah dan kemudian akan menghitungnya.

Dan ilustrasi berikut merepresentasikan sebuah map.

peta_ilustrasi

Pada ilustrasi di atas, secara otomatis program akan memberitahukan bahwa area yang sedang terjadi perang ada 5 petak. Sekarang pertanyaannya, bagaimana itu bisa dilakukan? Algoritma apa yang dipakai untuk mengimplementasikan program ini??

Cara yang digunakan di sini adalah menggunakan algoritma DFS (Depth First Search). DFS akan men-scan seluruh peta dengan cara rekursi dan akan membuat sebuah traversing pada peta tersebut.

Langkah-langkah scan pada DFS dilakukan oleh masing-masing pixel yang ada di gambar di atas. Untuk menentukan jumlah wilayah perang, karakter yang dicari adalah wilayah karakter ‘#’. Karakter ‘#’ mempunyai 4 arah gerak, yaitu atas, kanan, bawah, dan kiri. Kira-kira begini ilustrasinya.

Direct-pixel

Urutan pencarian, dilakukan dari atas (Up), kanan (Right), bawah (Down), dan kiri (Left). Jika pada salah satu elemen ditemukan karakter ‘#’ lagi, maka dilakukan pencarian ulang dengan dimulai dari karakter yang telah ditemukan tadi. Teknik yang digunakan di sini adalah teknik rekursi.

Step-stepnya adalah sebagai berikut

step-1Scan elemen-elemen yang berada di dekatnya secara langsung. Di sini tetangga yang bersifat diagonal tidak dihitung. Jangan lupa, tambahkan area dengan 1 (berarti area perang bertambah 1).

step-2

Scan atas, ternyata bukan merupakan karakter ‘#’

step-3Scan tetangga kanan, ternyata juga bukan merupakan  karakter ‘#’

step-4

step-5

Scan bawah, karena tetangga bawah merupakan karakter ‘#’, maka dilakukan fungsi DFS yang sama dengan menggunakan teknik rekursi. Dan traversing dimulai dari karakter berikutnya.

step-6

step-7

step-8

step-9

step-10

Dan seterusnya sampai karakter terakhir..

Implementasi dengan C/C++

/*
Simple Mapping With C/C++
Sepuluh Nopember Institute Of Technology, Surabaya, Indonesia
Author  : Fadlika Dita Nurjanto
Blog    : fadlikadn.wordpress.com
Email   : fadlikadn@gmail.com
*/
#include <stdio.h>
#include <cstring>
#define MAX 1000
int flag[MAX+1][MAX+1];
char chr[MAX+1][MAX+1];
char arr_chr[27];
int arr_int[27];

//DFS function dengan rekursi
void dfs(int row, int col, int h_loc, int w_loc,char search_chr)
{
	flag[row][col] = 1;
	//up
	if(row!=0)
	{
		if(flag[row-1][col]==0 && chr[row-1][col]==search_chr)
		    dfs(row-1,col,h_loc,w_loc,search_chr);
	}
	//right
	if(col+1<w_loc)
	{
		if(flag[row][col+1]==0 && chr[row][col+1]==search_chr)
		    dfs(row,col+1,h_loc,w_loc,search_chr);
	}
	//down
	if(row+1<h_loc)
	{
		if(flag[row+1][col]==0 && chr[row+1][col]==search_chr)
		    dfs(row+1,col,h_loc,w_loc,search_chr);
	}
	//left
	if(col!=0)
	{
		if(flag[row][col-1]==0 && chr[row][col-1]==search_chr)
		    dfs(row,col-1,h_loc,w_loc,search_chr);
	}

}

int main()
{
	int N,W,H,i,j,k,o,a=1;
	int into_array;
	int sum;
	printf("Jumlah Perulangan : ");
	scanf("%d",&N);
	for(i=1;i<=N;i++)
	{
	    printf("Dimensi Peta (H-Baris & W-Kolom)\n");
		scanf("%d %d",&H,&W);
		sum = 0;
		memset(flag,0,sizeof(flag));
		memset(chr,'0',sizeof(chr));
		for(j=0;j<H;j++)
		{
			scanf("%s",chr[j]);
		}
		printf("War Area #%d\n",a);
		a++;
		for(j=0;j<H;j++)
		{
			for(k=0;k<W;k++)
			{
			    if(flag[j][k]==0)
			    {
			        if(chr[j][k] == '#')
			        {
			            sum++;
			            dfs(j,k,H,W,chr[j][k]);
			        }
			    }
			}
		}
		printf("Jumlah Wilayah Perang : %d\n\n",sum);
	}
	return 0;
}

Artikel juga bisa didownload di sini

Iklan

10 thoughts on “Pemetaan Area (Mapping) Sederhana Dengan C/C++

    […] Penjelasan Algoritma DFS dan source code bisa didownload di sini. Artikel juga bisa dibaca di https://fadlikadn.wordpress.com/2011/06/12/simple_mapping_c/. Semoga bermanfaat, […]

    […] Penjelasan Algoritma DFS dan source formula bisa didownload di sini. Artikel juga bisa dibaca di https://fadlikadn.wordpress.com/2011/06/12/simple_mapping_c/. Semoga bermanfaat, […]

    MENONE said:
    13 Juli 2011 pukul 09:32

    wiiiiiiiiiiihhhhhhhhhhhhhhh…… apaan nich sob ga paham hehehehhehehehe

    Salam persahabatan selalu dr MENONE

      Fadlika Dita Nurjanto responded:
      13 Juli 2011 pukul 11:26

      oke…sama2…
      ini pake algoritma DFS, untuk mencari traversing..
      pake rekursi (pemanggilan fungsi berulang-ulang).. 😀

    […] dengan C/C++ view source […]

    Ahmad Nugraha said:
    8 Desember 2011 pukul 08:56

    pusing sAya kk

    missputriie said:
    29 Desember 2011 pukul 15:43

    kok pas di compile eror sih yaa… di bagian line
    int flag[MAX+1][MAX+1];
    char chr[MAX+1][MAX+1
    peringatannya array size too long…
    gmnaa tuhhh??

    zaqiaarizky said:
    8 Maret 2012 pukul 16:23

    maaf.. ada yang bsa bantu skripsi teknk informatika ga?

    […] Penjelasan Algoritma DFS dan source code bisa didownload di sini. Artikel juga bisa dibaca di https://fadlikadn.wordpress.com/2011/06/12/simple_mapping_c/. Semoga bermanfaat, […]

    Adithya irawan said:
    15 Desember 2012 pukul 18:00

    Mantep gan…

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s