Kepengen nulis pembahasan soal programming lagi. Kali ini temanya tentang matriks string. Jujur sebelumnya saya lemah sekali, bahkan ketika final compfest kemarin pun saya tidak tahu apa-apa tentang implementasi matriks yang berupa string, makanya soal termudah final compfest 2013 (yang berupa matriks string) tidak bisa saya kerjakan :(. Oleh karena itu saya ingin sedikit sharing beberapa soal matriks string yang sudah saya kerjakan, yaitu soal pertama final compfest kemarin dan soal qualification round facebook hacker cup 2014.
Oke, langsung aja. Berikut pembahasannya
1. Laser Ajaib – Soal Final Compfest 2013
Soal :
Di masa depan, tepatnya tahun 20XX, polisi memiliki senjata canggih untuk menumpas kejahatan. Senjata tersebut diberi nama “laser ajaib”. Tidak seperti laser pada masa kini yang
hanya bisa menembak lurus, laser ajaib bisa menembak secara berbelok-belok. Akan tetapi, kelemahan dari laser ajaib ini adalah lasernya bisa terputus di tengah jalan sehingga tidak kena sasaran. Pak Chanek, sebagai seorang polisi di masa depan, ingin mengetahui apakah laser
ajaib miliknya kena sasaran atau tidak.Diberikan sebuah pemetaan dari hasil tembakan laser ajaib. Pemetaan dari laser ajaib tersebut
memenuhi aturan sebagai berikut:
• Terdiri dari N baris dan M kolom
• Karakter ‘-‘ menyatakan daerah kosong, dan karakter ‘#’ menyatakan daerah yang ada
dalam pengaruh laser ajaib
• Dalam satu kolom, dijamin hanya ada satu karakter ‘#’, atau tidak ada sama sekali
• Dijamin terdapat setidaknya satu karakter ‘#’ pada suatu pemetaan
Laser di suatu kolom dianggap “menyambung” apabila setelah karakter ‘#’ di kolom itu, ada karakter ‘#’ lain yang berada tepat di kolom berikutnya (boleh pada baris yang sama, satu baris di atasnya, atau satu baris di bawahnya, selama masih belum keluar dari pemetaan).
Pengecualian pada kolom terakhir, yang selalu akan dianggap menyambung. Laser ajaib dianggap kena sasaran apabila seluruh kolom di pemetaan itu memiliki karakter ‘#’, dan
menyambung.
Tugas Anda adalah memeriksa apakah hasil tembakan itu kena sasaran atau tidak!Format Masukan
Baris pertama berisi sebuah bilangan bulat T, yaitu banyaknya kasus uji.
Untuk setiap kasus uji:
Baris pertama berisi dua buah bilangan bulat yang dipisahkan oleh spasi, yaitu N dan M.
N baris berikutnya berisi M karakter, yang merupakan pemetaan dari laser ajaib.Format Keluaran
Untuk setiap kasus uji, keluarkan “KENA” jika pada kasus tersebut tembakan laser ajaib kena
sasaran. Jika tidak, keluarkan “TIDAK KENA”.Contoh Masukan
2
10 10
———-
———-
———-
-#–##—-
#-##–#—
——-##-
———#
———-
———-
———-
5 20
—##—##–##-#####
-##–###–##–#—–
——————–
——————–
——————–Contoh Keluaran
KENA
TIDAK KENA
Yang bisa ditangkap dari soal ini adalah, menentukan apakah dari x awal sampai x akhir ‘#’ tidak putus. Solusinya adalah menentukan terlebih dahulu dari titik x=0, cari dari y awal sampai y akhir apakah ada char ‘#’. Jika tidak ada, maka outputkan langsung TIDAK KENA, tapi apabila ada, lalu pindah lagi ke koordinat x selanjutnya, dan y menjadi 0. Cari lagi tanda ‘#’. Jika ketemu, maka selisihkan antara koordinat y sekarang dengan y sebelumnya. Jika nilainya lebih besar dari 1 atau lebih kecil dari -1, maka outputkan program dengan TIDAK KENA dan program berhenti. Jika tidak, maka lanjutkan hingga nilai x==n. Jika nilai x==n, maka program berhenti dan kena=benar. Maka outputkan KENA.
Kode :
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int t;
cin >> t;
for (int i=1;i<=t;i++) {
int n,m;
cin >> n >> m;
string s[n];
for (int j=0;j<n;j++) cin >> s[j];
int x=0,y=0;
bool ketemu,kena;
ketemu=false,kena=false;
while (!ketemu && y<n) {
if (s[y][x]=='#') ketemu=true;
else y++;
}
bool kelar,dapet;
if (ketemu) {
kelar=false;
x++;
int ybef=y;
y=0;
while (!kelar) {
dapet=false;
while (!dapet && y<n) {
if (s[y][x]=='#') dapet=true;
else y++;
}
if (!dapet) kelar=true;
else {
if (y-ybef>1 || y-ybef<-1) kelar=true;
else {
x++;
ybef=y;
y=0;
}
}
if (!kelar && x==m) {
kelar=true;
kena=true;
}
}
}
else kena=false;
if (kena) cout << "KENA" << endl;
else cout << "TIDAK KENA" << endl;
}
}
2. Square Detector – Qualification Round Facebook Hacker Cup 2014
Soal :
You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.
You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.
Input
The first line of the input consists of a single number T, the number of test cases.
Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either “.” symbolizing a white cell, or “#” symbolizing a black cell. Every test case contains at least one black cell.
Output
For each test case i numbered from 1 to T, output “Case #i: “, followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells.
Example Input
5 4 ..## ..## .... .... 4 ..## ..## #... .... 4 #### #..# #..# #### 5 ##### ##### ##### ##### ..... 5 ##### ##### ##### ##### ##### Example Output Case #1: YES Case #2: NO Case #3: NO Case #4: NO Case #5: YES
Sebenarnya kode ini belum disubmit karena telat submit (batas submit cuma 6 menit dan saya kelamaan bikin file output), jadi gak tahu bener apa enggak. Tapi di testcase contoh, semuanya benar.
Lanjut. Jadi inti dari soal ini adalah menentukan apakah tanda ‘#’ membentuk persegi atau tidak. Solusinya, pertama kita cari dulu titik kiri atas (x awal dan y awal) dari ‘#”. Jika ketemu, lalu cari x akhir dan y akhir. Setelah itu, jika x akhir – x awal != y akhir – y awal, hentikan program dan outputkan NO karena sudah pasti bukan persegi. Jika tidak, maka ada beberapa kasus. Yang pertama adalah apabila ditengah-tengah persegi terdapat char ‘.’, dan kasus yang kedua adalah apabila ada tanda ‘#’ lain diluar persegi.
Kode :
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int t;
cin >> t;
for (int i=1;i<=t;i++) {
int n;
cin >> n;
string s[n];
bool kotak[n][n];
for (int j=0;j<n;j++) {
for (int k=0;k<n;k++) {
kotak[j][k]=false;
}
}
for (int j=0;j<n;j++) cin >> s[j];
bool ketemu=false,kelar=false;
int x=0,y=0; //koordinat
while (!ketemu && !kelar) {
if (y==n-1 && x==n-1) kelar=true;
if (s[y][x]=='#') ketemu=true;
else if (y==n-1) {
x=0;;
y++;
}
else x++;
}
int xx=x,yy=y; //xx = x akhir,yy = y akhir
while (s[y][xx]=='#') xx++;
xx--;
while (s[yy][x]=='#') yy++;
yy--;
for (int k=y;k<=yy;k++) {
for (int l=x;l<=xx;l++) {
kotak[k][l]=true;
}
}
bool benar=false;
if (xx-x==yy-y) {
//ngecek apa tengahnya kosong
bool muncul=false,sudah=false;
int tx=x,ty=y;
while (!muncul && !sudah) {
if (ty==yy && tx==xx) sudah=true;
if (s[ty][tx]=='.') muncul=true;
else if (tx==xx) {
tx=x;
ty++;
}
else tx++;
}
if (!muncul) benar=true;
}
//cari '#' yang nyampah di petak lain
bool nyampah=false,tamat=false;
int cariy=0,carix=0;
while (!nyampah && !tamat) {
if (cariy==n-1 && carix==n-1) tamat=true;
if (s[cariy][carix]=='#' && !kotak[cariy][carix]) nyampah=true;
else if (carix==n-1 && cariy!=n-1) {
carix=0;
cariy++;
}
else carix++;
}
if (nyampah) benar=false;
if (benar) cout << "Case #" << i << ": YES" << endl;
else cout << "Case #" << i << ": NO" << endl;
}
}
~~~
Sekian dari pembahasan ini. Kritikan, masukan, dan saran sangat ditunggu. Terimakasih 😀
Sat's Blog 
You must be logged in to post a comment.