Jun 12 学习笔记

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100 + 5;

char pic[maxn][maxn];
int m, n, idx[maxn][maxn];

void dfs(int r, int c, int id) {
if(r < 0 || r >= m || c < 0 || c >= n)
    return;
if(idx[r][c] != -1 || pic[r][c] != '@')
    return;
idx[r][c] = id;
for(int dr = -1; dr < 2; dr++)
    for(int dc = -1; dc < 2; dc++)
        if(dr != 0 || dc != 0) dfs(r + dr, c + dc, id);
}

int main() {
scanf("%d%d", &m, &n);
for(int i = 0; i < m; i++) {
    scanf("%s", pic[i]);
}
memset(idx, -1, sizeof(idx));
int cnt = 0;

for(int i = 0; i < m; i++)
    for(int j = 0; j < n; j++)
        if(pic[i][j] == '@' && idx[i][j] == -1)
            dfs(i, j, ++cnt);

printf("%d\n", cnt);
return 0;
}

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 100 + 5;

struct cell {
int r;
int c;
};

char pic[maxn][maxn];
int m, n, distx[maxn][maxn];
queue<cell> checkQueue;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main() {
scanf("%d%d", &m, &n);
for(int i = 0; i < m; i++) {
    scanf("%s", pic[i]);
}
memset(distx, -1, sizeof(distx));
int cnt = 0;

cell begin;
begin.r = 0;
begin.c = 0;
distx[0][0] = 0;

checkQueue.push(begin);
while(!checkQueue.empty()) {
    cell x = checkQueue.front();
    checkQueue.pop();
    for(int i = 0; i <= 3; i++) {
        int r = x.r + dr[i];
        int c = x.c + dc[i];
        if(r < 0 || r >= m || c < 0 || c >= n) continue;
        if(pic[r][c] == '0') continue;
        if(distx[r][c] == -1) {
            cell ncell;
            ncell.r = r;
            ncell.c = c;
            checkQueue.push(ncell);distx[r][c] = distx[x.r][x.c] + 1;
        }
    }
}
printf("%d\n", distx[m - 1][n - 1]);
for(int i = 0; i < m; i++) {
    for(int j = 0; j < n; j++)
        printf("%d\t", distx[i][j]);
    printf("\n");
}
return 0;
}