AOJ 0067 - The number of island
深さ優先探索を初めて解いた。
#include <iostream> std::string map[12]; void dfs(int x,int y){ if(x-1>=0&&map[y][x-1]=='1')map[y][x-1]='0',dfs(x-1,y); if(x+1<=11&&map[y][x+1]=='1')map[y][x+1]='0',dfs(x+1,y); if(y-1>=0&&map[y-1][x]=='1')map[y-1][x]='0',dfs(x,y-1); if(y+1<=11&&map[y+1][x]=='1')map[y+1][x]='0',dfs(x,y+1); return ; } int main(){ while(1){ for(int i=0;i<12;i++){ std::cin>>map[i]; } if(std::cin.eof())return 0; int r = 0; for(int y=0;y<12;y++){ for(int x=0;x<12;x++){ if(map[y][x]=='1'){ r++,map[y][x]='0',dfs(x,y); } } } std::cout<<r<<std::endl; } }
蟻本に同じ問題があったような気がした。
これで530byteぐらいだったと思う。
短さを目指し様々な技を使う。
#include<iostream> std::string m[12]; void d(int x,int y){ if(x&&m[y][x-1]-48)m[y][x-1]=48,d(x-1,y); if(x<11&&m[y][x+1]-48)m[y][x+1]=48,d(x+1,y); if(y&&m[y-1][x]-48)m[y-1][x]=48,d(x,y-1); if(y<11&&m[y+1][x]-48)m[y+1][x]=48,d(x,y+1); return ; } main(){ while(1){ int y=12,r=0; for(;y;y--)std::cin>>m[y-1]; if(std::cin.eof())return 0; for(;y<12;y++)for(int x=0;x<12;x++)if(m[y][x]-48)r++,m[y][x]=48,d(x,y); std::cout<<r<<'\n'; } }
415byteでした。ランキングは8位です。
166byteはどうやっているんだろう。C++はしっかり監視してくるので、ShortCodingが難しい。(加筆 121028)