Hdu 1241 - Oil Deposits

1407 단어
샅샅이 뒤지다
부끄럽다. 이 문제 이전의 코드는 테스트 데이터도 넘지 못해서 나도 뜻밖에도 썼다. 만약 검색을 복습하지 않았더라면 나도 이 버그를 발견하지 못했을 것이다.
내 블로그는 모두 양심에 따라 쓴 것이고, 모든 코드는 AC를 할 수 있다!만약 네가 CE라면 다른 언어로 바꾸어 봐라!
 
 
검색할 때 검색한 점을 다른 기호로 바꾸어 중복 검색을 피한다.
상하좌우와 대각선에 인접한 점이 있기 때문에 8개 방향을 검색해야 한다.
 
AC 코드:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

char map[105][105];
int n, m;
int dir[8][2] = { {-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1} } ;

bool inmap(int x,int y) {
    if(x<0 || y<0 || x>=m || y>=n) return false;
    return true;
}

void dfs(int x, int y) {
    int xx, yy, i;
    for(i=0; i<8; i++) {
        xx = x + dir[i][0];
        yy = y + dir[i][1];
        if(inmap(xx, yy) && map[xx][yy] == '@') {
            map[xx][yy] = '*';
            dfs(xx, yy);
        }
    }
}

int main() {
    int i, j, cnt;
    while(scanf("%d%d",&m,&n)!=EOF) {
        if(!m) break;
        getchar();
        for(i=0; i<m; i++)
            scanf("%s",map[i]);
        cnt = 0;
        for(i=0; i<m; i++) {
            for(j=0; j<n; j++) {
                if(map[i][j] == '@') {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d
",cnt); } return 0; }

좋은 웹페이지 즐겨찾기