이것 저것 &

문제링크: https://www.acmicpc.net/problem/12886

체감 골3 이상이었던 bfs 문제 ㅠㅠ

접근방식

1. dp방식, bfs방식 등이 가능할 것 같았다. 

2. 만만한 bfs로 도전

만약 a, b, c의 총합이 3으로 딱 나눠떨어지지 않는다면 무조건 결과는 0이다. 

1000x1000x1000 배열을 생성하게 되면 메모리 초과이다. 

이때, 총합의 합이 같기 때문에 1000x1000만으로도 a,b,c의 값을 저장할 수 있다는 것을 파악해야 한다.

큐에 들어가는 값은 정렬을 하여서 사용한다.

그 이유는 중복을 방지하기 위함과 런타임에러(OutOfBounds)를 방지하기 위함

문제풀이 

1.  큐를 사용한 bfs 구현

2. y_ar과 x_ar를 통해서 현재 값을 기준으로 탐색해야 하는 값들을 도출

정답코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int visited[1001][1001] = { 0, };
int a, b, c, d = 0;

int bfs() {

	queue <pair<int, int>> que;
	que.push(make_pair(a, b));
	visited[a][b] = 1;

	while (!que.empty()) {
		int ca = que.front().first;
		int cb = que.front().second;
		int cc = d - ca - cb;
		que.pop();

		if (ca == cb && ca == cc)
			return 1;

		int n_x[3] = { ca,ca,cb };
		int n_y[3] = { cb,cc,cc };

		for (int i = 0; i < 3; i++) {
			int na = n_x[i];
			int nb = n_y[i];
			if (na < nb)
				nb -= na, na += na;
			else if (na > nb)
				na -= nb, nb += nb;
			else
				continue;
			int nc = d - na - nb;

		
			int ra = min(min(na, nb), nc);
			int rb = max(max(na, nb), nc);

			if (visited[ra][rb] == 0) {
				visited[ra][rb] = 1;
				que.push(make_pair(ra, rb));
			}

		}


	}

	return 0;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> a >> b >> c;
	d = a + b + c;

	if ((a + b + c) % 3 != 0)
		cout << 0 << endl;
	else
		cout << bfs() << endl;
	

	return 0;
}

문제링크: https://www.acmicpc.net/problem/3108

전형적인 한붓그리기 문제라고 하는데 어려움을 겪었습니다.

마이너스 좌표는 +500을 더해줌으로 해결했는데,

아래와 같은 그림에서 멘붕이 왔습니다.

위 처럼 네모가 둘이 붙어있으면 일반  탐색으로는 붙어 있는 걸로 처리 되었기 때문입니다.

이를 해결하기 위해서  동서남북 4방향을 저장하는 배열을 작성하면서 제작하려 해보았지만, 

실패...

얍문님 티스토리를 통해서 좌표값에 2배를 곱해줌으로서 쉽게 이러한 문제를 해결할 수 있단 걸 

알게되었습니다. (감사함다.)

접근방식

1. 좌표값을 (a + 500) * 2로 만든후 직사각형들을 색칠

2. 일반 bfs를 통해서 연결된 도형들을 탐색하면서 갯수를 세어주자

문제풀이 

1. 좌표값에 (a + 500) * 2 를 해주기

2. (0,0) 좌표인 arr[1000][1000]을 미리 bfs로 탐색해주기.

( 제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다. )

3. 0,0부터 2000,2000까지 bfs로 탐색하면서 뭉쳐진 도형들을 색칠해주며 갯수 세기

아래는 정답 코드

#include <iostream>
#include <queue>
using namespace std;

int n, result ;
int x1, y11, x2, y2;

bool arr[2001][2001] = { 0, };
bool visited[2001][2001] = { 0, };

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };


void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny > 2000 || nx < 0 || nx > 2000)
				continue;
			if (visited[ny][nx] != 0 || arr[ny][nx] != 1)
				continue;
			visited[ny][nx] = 1;
			que.push(make_pair(ny, nx));

		}



	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {

		cin >> x1 >> y11 >> x2 >> y2;
		x1 = (x1 + 500) * 2;
		y11 = (y11 + 500) * 2;
		x2 = (x2 + 500) * 2;
		y2 = (y2 + 500) * 2;

		for (int i = x1; i <= x2; i++) {
			arr[y11][i] = 1;
			arr[y2][i] = 1;
		}
		for (int i = y11; i <= y2; i++) {
			arr[i][x1] = 1;
			arr[i][x2] = 1;
		}
	}

	
	if(arr[1000][1000] == 1)
		bfs(1000, 1000);

	for (int i = 0; i <= 2000; i++)
		for (int j = 0; j <= 2000; j++)
			if (arr[i][j] == 1 && visited[i][j] == 0) {
				bfs(i, j);
				result++;
			}

	cout << result << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/16946

사소한 부분에서 틀렸던 문제...

4일 동안 반례를 못찾고 시름시름 앓고 있었는데, bamgoesn 님께서 반례를 찾아주셨다. ㅠㅠ

다시 한번 감사드립니다. ㅠㅠ

구현 + bfs 문제입니다. 

어떻게 보면 시뮬레이션이기도 하고, bfs 심화같기도 한 문제.

접근방식

1. 우선 빈칸들의 좌표별로 이동가능한 값들을 저장해야한다.

이때, 구획별로 번호를 매겨주어서 벽을 허물었을 때, 중복으로 구획을 세지 않도록 한다.

2. 벽을 하나씩 부서보면서 해당하는 좌표의 값을 도출한다. 

문제풀이 

1. bfs를 통해서 빈 좌표별로 이동가능한 최대한 값을 도출한다.

2. 다시 한번 bfs를 통해 이번엔 구획에 해당하는 모든 값들에 이동가능한 값과 구획번호를 저장

3. 벽 좌표를 vector에 저장하고 하나씩 부서보면서 결과를 도출

이때, 구획번호가 중복이 되지 않겠끔 vector에 구획번호를 저장하면서 4방향을 모두 확인 

정답코드입니다. 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int n, m;
int arr[1001][1001] = { 0, };
vector <pair<int, int>> block;
int result[1001][1001] = { 0, };

int visited[1001][1001][2] = { 0, }; // 첨에는 이동 가능한 개수를 저장할거고, 두번째에는 고유 영역 값을 저장할 예정
int vis_cnt = 1; // 구획의 첫 번호는 1부터 

bool temp_v[1001][1001] = { 0, }; //난 bfs로 구현할거야, 얘는 탐색을 위해 사용할 배열

int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };


void bfs(int ty, int tx) {

	// 1. temp_v를 사용해서 이동 가능한 개수 파악하기
	int maxed = 1;
	temp_v[ty][tx] = 1;
	queue <pair<int, int>> que;
	que.push(make_pair(ty, tx));

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (temp_v[ny][nx] != 0)
				continue;
			temp_v[ny][nx] = 1;
			que.push(make_pair(ny, nx));
			maxed++;
		}
	}
	//cout << maxed << endl;

	// 2. visited에 이동가능한 개수와 자신의 구획번호를 입력하기 
	visited[ty][tx][0] = maxed;
	visited[ty][tx][1] = vis_cnt;
	que.push(make_pair(ty, tx));

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (visited[ny][nx][0] != 0)
				continue;
			visited[ny][nx][0] = maxed;
			visited[ny][nx][1] = vis_cnt;
			que.push(make_pair(ny, nx));
		}
	}



	vis_cnt++; //인덱스를 하나 올려준다.


}

int main() {
	ios_base::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 1)
				block.push_back(make_pair(i, j));
		}
	}

	//cout << block.size() << endl;

	//1. 영역별로 마킹하기!

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (temp_v[i][j] == 0 && arr[i][j] == 0) { // 벽이 아니고, 방문한 적이 없다면 탐색해야해!
				bfs(i, j);
			}

	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << visited[i][j][1] << ' ';
		}
	cout << endl;
	}
	*/

	//2. 벽을 하나씩 부수면서 이동가능한 결과값을 도출하는 과정 

	vector <int> index; // index 값들을 임시 저장할 친구 
	for (int i = 0; i < block.size(); i++) {
		index.clear();
		int val = 1; //자신을 포함해야 하니 1 부터 시작한다. 
		
		int y = block[i].first;
		int x = block[i].second;

		for (int j = 0; j < 4; j++) {
			bool flag2 = true;
			int ny = y + y_ar[j];
			int nx = x + x_ar[j];

			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] == 1)
				continue;
			for (int i = 0; i < index.size(); i++)
				if (visited[ny][nx][1] == index[i]) {
					flag2 = false;
					break;
				}
			if (flag2 == true) {
				val += visited[ny][nx][0];
				index.push_back(visited[ny][nx][1]);
			}
			
		}

		result[y][x] = val % 10;
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%d", result[i][j]);
		printf("\n");
	}

}

문제링크: https://www.acmicpc.net/problem/14466

문제를 이해하는데 오래 걸렸습니다.

즉 N x N 구역의 좌표들에 소가 분포해있습니다.

문제에서 주어지는 길을 피해서 이동하여 소들은 만날 수가 있겠죠.

하지만 특정한 소들은 꼭 길을 포함해서 이동할때에만 만날 수가 있습니다.

그 소의 개수를 출력하라는 문제입니다.

문제에서 주어진 예시에서는 

A(3,3), B(2,2), C(2,3)  이렇게 3마리 소가 있습니다. 

B(2,2)와 C(2,3)는 2,2 -> 1,2 -> 1,3 -> 2,3 경로로 움직여서 길을 포함하지 않더라도 만날 수 있습니다.

하지만 A,B와 A,C는 길을 포함하지 않고 만날 수 가 없습니다. 

그래서 총 2쌍이라는 겁니다.

접근방식

1. 일반적인 bfs로 구현해보자

문제풀이 

1. 길을 마킹할 배열 arr[101][101][4] 를 생성 북,동,남,서 순으로 이동이 불가한 위치를 표시할 용도

2. bfs를 통해 소 기준으로 이동이 불가한 소들을 도출

3. bfs를 반복해줄때, 이전 소들은 확인할 필요없이 자신보다 인덱스가 높은 소들만 확인해주면서 넘어가야 중복이 안생김

코드를 직접 확인하는게 더 빠를 것 같음

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, k, R;
int arr[101][101][4] = { 0, }; // 4방향에 대해서 길이 있을 수 있으니.. 북 동 남 서 순으로 저장할거
bool visited[101][101];
int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

vector <pair<int, int>> cow;
int result = 0;
void bfs(int sy, int sx) {

	queue <pair<int, int >> que;
	que.push(make_pair(sy, sx));
	visited[sy][sx] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			if (arr[cy][cx][i] == 1) continue; //도로가 있는건 탐색 안해줄거야
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny <1 || ny > n || nx < 1 || nx > n || visited[ny][nx] == 1)
				continue;
			que.push(make_pair(ny, nx));
			visited[ny][nx] = 1;
		}



	}


}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> R;

	int r, c, rr, cc;
	for (int i = 0; i < R; i++) {
		cin >> r >> c >> rr >> cc;
		for (int j = 0; j < 4; j++) {
			int nr = r + y_ar[j];
			int nc = c + x_ar[j];
			if (nr == rr && nc == cc) {
				arr[r][c][j] = 1; // 다리 생성
				arr[rr][cc][(j + 2)%4] = 1;
			}
		}
	}

	for (int i = 0; i < k; i++) {
		cin >> r >> c;
		cow.push_back(make_pair(r, c)); 
	}

	for (int i = 0; i < k; i++) {
		memset(visited, 0, sizeof(visited));
		bfs(cow[i].first, cow[i].second);

		for (int j = i + 1; j < k; j++) {
			if (visited[cow[j].first][cow[j].second] == 0)
				result++;
		}
	}


	cout << result << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/16954

bfs, 시뮬레이션 문제

접근방식

1. 욱제라는 사람의 이동은 bfs로 구현이 가능

2. 욱제이동과 벽이동을 번갈아가며 진행하면서 결과값을 도출하자

문제풀이 

1. bfs를 통해서 이동이 가능한 경로를 저장하며 진행

이때, 방문노드는 매턴마다 초기화하는데 그 이유는 다음턴에 다시 해당좌표로 이동할수도 있기 때문

........

........

........

........

........

.#######

#.......

........

ex) 위와 같은 예제에서 첨좌표로 되돌아 오는 것

2. 벽이동은 벽좌표들을 vector에 넣어 관리하며 진행 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
using namespace std;

typedef struct a {
	int y;
	int x;
}dir;

dir d[9] = { {0,0}, {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
string arr[8]; // 0base; 시작점은 7,0 도착점은 0,7 이다.
vector <dir> vec; // 벽을 저장할 벡터
queue <dir> que;

bool result = 0;
bool visited[8][8];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	for (int i = 0; i < 8; i++) {
		cin >> arr[i];
		for (int j = 0; j < 8; j++) {
			if (arr[i][j] == '#')
				vec.push_back({ i,j });
		}
	}
	que.push({ 7,0 });

	while (!que.empty()) { //큐가 비었으면 종료되는 구조 

		//1. 욱제의 이동
		int cnt = que.size();
		memset(visited, 0, sizeof(visited));

		while (cnt--) { // 갯수만큼

			int y = que.front().y;
			int x = que.front().x;
			que.pop();
			

			if (y == 0 && x == 7) {
				result = true;
				break;
			} 
			if (arr[y][x] == '#') //벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.
				continue;

			for (int i = 0; i < 9; i++) {
				int ny = y + d[i].y;
				int nx = x + d[i].x;
				if (ny < 0 || ny > 7 || nx < 0 || nx > 7 || arr[ny][nx] == '#') //방문여부는 체크하지 않는다 왔다 갔다 할수도 있자나 
					continue;
				if (visited[ny][nx] == 1)
					continue;
				visited[ny][nx] = 1;
				que.push({ ny,nx });
			}
		}

		//2. 벽이동
		
		for (int i = 0; i < 8; i++)
			arr[i] = "........";
		for (int i = 0; i < vec.size(); i++) {
			int y = vec[i].y;
			int x = vec[i].x;

			if (y == 7) {
				vec.erase(vec.begin() + i);
				i--;
			
				continue;
			}


			arr[y + 1][x] = '#';
			vec[i].y++;

		}

		if (result == true) //도달했으면 조기종료 
			break;
		
		/*
		cout << endl;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++)
				cout << visited[i][j];
			cout << endl;
		}
		cout << endl;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++)
				cout << arr[i][j];
			cout << endl;
		}
		cout << "quesize " << que.size() << endl;
		*/
	}


	cout << result << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/2151

bfs문제

6087번 레이저 통신과 흡사 

접근방식

1. bfs를 통해서 접근하는 방법을 고안

2. 방향마다 visited(방문값)을 구해주며 진행하여 결과값을 도출하자

문제풀이 

1. 큐에는 현재 좌표, 거울의 개수 순으로 저장

2. visited에는 4방향별로 최소값을 적으며 bfs를 진행

코드로 이해하는게 더 빠를 것 같음

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct a {
	int y;
	int x;
}dir;

int n;
string arr[50];
vector <dir> door;
int visited[50][50][4];
dir d[4] = { {0,1},{1,0},{0,-1},{-1,0} };

void bfs() {

	queue <pair<pair<int, int>,int>> que; // 좌표 방향
	for (int i = 0; i < 4; i++) {
		que.push(make_pair(make_pair(door[0].y, door[0].x),i));
		visited[door[0].y][door[0].x][i] = 1;
	}

	while (!que.empty()) {
		int y = que.front().first.first;
		int x = que.front().first.second;
		int dir = que.front().second;
		que.pop();

		int ny = y + d[dir].y;
		int nx = x + d[dir].x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= n || arr[ny][nx] == '*')
			continue;

		if (arr[ny][nx] == '.' || arr[ny][nx] == '#') {
			if (visited[ny][nx][dir] > visited[y][x][dir] ||  visited[ny][nx][dir] == 0) {
				visited[ny][nx][dir] = visited[y][x][dir];
				que.push(make_pair(make_pair(ny, nx), dir));
			}
		}
		else if (arr[ny][nx] == '!') {
			if (visited[ny][nx][dir] > visited[y][x][dir]) { //거울 설치 x 
				visited[ny][nx][dir] = visited[y][x][dir];
				que.push(make_pair(make_pair(ny, nx), dir));
			}
			for (int i = 1; i <= 3; i += 2) {
				if (visited[ny][nx][(dir + i) % 4] > visited[y][x][dir] + 1) { // 거울 설치 1
					visited[ny][nx][(dir + i) % 4] = visited[y][x][dir] + 1;
					que.push(make_pair(make_pair(ny, nx), (dir + i) % 4));
				}
			}
			
		}

	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == '#')
				door.push_back({ i,j });
			for (int k = 0; k < 4; k++)
				visited[i][j][k] = 2000000000;
		}
	}

	bfs();


	int result = 2000000000;
	for (int i = 0; i < 4; i++) {
		if(visited[door[1].y][door[1].x][i] != 0)
			result = min(result, visited[door[1].y][door[1].x][i]);
	}
	cout << result - 1 << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1039

bfs문제입니다.

접근방식

1. 일반적인 공식이나 규칙을 통해서 풀 수 있는 문제가 아님

132 3

이라는 입력값일때, 결과는 321이 아닌 312

312 -> 321 -> 312 이기 때문에

즉, 특정 규칙을 통해서가 아닌 모든 경우를 판단해서 최대값을 도출하는 방향으로 접근함

2. bfs를 통해서 매번 k번만큼 모든경우를 판단해줌 

visited는 k번마다 초기화를 시켜주어야함.

왜냐하면 앞선 예시에서 312라는 값이 앞에서 사용되어졌는데, 결과값이기도 함 

즉, 매번 방문여부를 초기화하며 진행해주어야함 

문제풀이 

1. 우선 -1인 경우를 생각해봄

• 한자리 수일때: 스왑할 수가 없으니 불가
• 두자리 수이고 일의 자리수가 0일때: 스압하게 되면 0이 앞으로 나옴으로 조건에 부합하지 않음 ex) 10, 20, 50

2. BFS를 통해서 구현함

이때, K번만큼 반복하도록 구획을 나눠주면서 진행해야함. 이유는 접근방식 2번 참고

3. BFS에서 문자열에서 한 문자씩 바꿔보면서 visited집합에 값이 있는지 없는지 판단하며 진행

정답 코드

#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

string arr;
int k;
int maxed = 0;
bool jud() {
	int cnt = 0;
	for (int i = 0; i < arr.size(); i++)
		if (arr[i] > '0')
			cnt++;
	if (cnt > 1)
		return true;
	return false;
}

void bfs() {
	queue <string> que;
	que.push(arr);

	for (int u = 0; u < k; u++) { // k번 반복 
		int sized = que.size();
		set <string> visitied;

		for (int s = 0; s < sized; s++) {
			string temp = que.front();
			que.pop();

			for (int i = 0; i < temp.size() - 1; i++) {
				for (int j = i + 1; j < temp.size(); j++) {
					if (i == 0 && temp[j] == '0') continue;

					swap(temp[i], temp[j]); // #include algo
					if (visitied.find(temp) == visitied.end()) {
						if (u == k - 1) { //마지막 턴
							int val = stoi(temp);
							maxed = max(maxed, val);
						}
						que.push(temp);
						visitied.insert(temp);
					}
					swap(temp[i], temp[j]);
				}
			}


		}



	}


}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> arr >> k;
	if (arr.size() == 1) { // 한자리 수
		cout << -1 << endl;
		return 0;
	}
	else if (arr.size() == 2 && jud() == false) { // 두자리 수이지만 수가 하나라 swap을 못할 때
		cout << -1 << endl;
		return 0;
	}

	bfs();

	cout << maxed << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/6087

bfs문제입니다.

접근방식

1. 결국 몇번 꺾여서 목표에 도달할 수 있는지 묻는 문제

2. bfs를 통해서 구현하기로 결정. 일반적인 형태라는 다르게 큐를 구현해야함

문제풀이 

1. 큐에는 현재 좌표, 거울의 개수, 도달한 방향순으로 저장

2. 만약 거울의 갯수가 같거나 작다면 큐에 넣어주면서 거울 갯수를 탐색

이때, visited함수에 최소 거울의 갯수를 저장

정답 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
char arr[100][100];

vector <pair<int, int>> laser;
int visited[100][100] = { 0, };
int w, h;

int val, temp;

void bfs() {

	queue <pair<pair<int, int>, pair<int, int>>> que; //좌표, 거울 갯수, 방향순으로 넣을거
	que.push(make_pair(make_pair(laser[0].first, laser[0].second), make_pair(0, -1)));

	while (!que.empty()) {
		int y = que.front().first.first;
		int x = que.front().first.second;
		int mirror = que.front().second.first;
		int dir = que.front().second.second;
		que.pop();
		int temp;
		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			if (ny < 0 || ny >= h || nx < 0 || nx >= w || arr[ny][nx] == '*' )
				continue;
			temp = mirror;
			if (dir != i)
				temp++;
			if (visited[ny][nx] >= temp) {
				visited[ny][nx] = temp;
				que.push(make_pair(make_pair(ny, nx), make_pair(temp, i)));
			}



		}

		
	}



}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		cin >> arr[i];
		for (int j = 0; j < w; j++) {
			if (arr[i][j] == 'C')
				arr[i][j] = '.', laser.push_back(make_pair(i, j));
			visited[i][j] = 1000000000;
			
		}
	}

	bfs();
	/*
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << visited[i][j] << ' ';
		}
		cout << endl;
	}
	*/

	cout << visited[laser[1].first][laser[1].second] - 1 << endl;

	return 0;
}