침대 밖은 위험해!

#include<iostream>
using namespace std;

int n, m, map[51][51], ans = 0;
int r, c, d;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

int main(void){
	freopen("text.txt", "r", stdin);
	cin >> n >> m;
	cin >> r >> c >> d;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	while (true){
		if (map[r][c] == 0){
			map[r][c] = 2;
			ans++;
		}

		int k = 0, nd, nr, nc;
		for (; k < 4; k++){
			d = (d + 3) % 4;
			nr = r + dr[d];
			nc = c + dc[d];

			if (map[nr][nc] == 0){
				r = nr; c = nc;
				break;
			}
		}

		if (k == 4){
			nr = r - dr[d];
			nc = c - dc[d];

			if (map[nr][nc] == 1){
				break;
			}

			r = nr;
			c = nc;
		}
	}
	cout << ans << "\n";
	return 0;
}

#include<iostream>
using namespace std;

int n, a[12], s[4];
long long ans_max = -1000000000, ans_min = 1000000000;

void dfs(int cnt, int sum){
	if (cnt == n - 1){
		if (sum < ans_min)
			ans_min = sum;
		if (ans_max < sum)
			ans_max = sum;
		return;
	}

	if (s[0] > 0){
		s[0]--;
		dfs(cnt + 1, sum + a[cnt + 1]);
		s[0]++;
	}
	if (s[1] > 0){
		s[1]--;
		dfs(cnt + 1, sum - a[cnt + 1]);
		s[1]++;
	}
	if (s[2] > 0){
		s[2]--;
		dfs(cnt + 1, sum * a[cnt + 1]);
		s[2]++;
	}
	if (s[3] > 0){
		s[3]--;
		dfs(cnt + 1, sum / a[cnt + 1]);
		s[3]++;
	}
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < 4; i++)
		cin >> s[i];

	dfs(0, a[0]);
	cout << ans_max << "\n";
	cout << ans_min << "\n";
}

#include<iostream>
using namespace std;

int n, s[21][21], teamA[21], teamB[21], ans = 987654321;

int abs(int a){
	return ((a < 0) ? -a : a);
}

int calScore(int team[21]){
	int temp = 0;
	for (int i = 0; i < n / 2 - 1; i++){
		for (int j = i + 1; j < n / 2; j++){
			temp += s[team[i]][team[j]] + s[team[j]][team[i]];
		}
	}
	return temp;
}

void dfs(int num, int cnt_a, int cnt_b){
	if (cnt_a == n / 2 && cnt_b == n / 2){
		int score_a = calScore(teamA);
		int score_b = calScore(teamB);
		if (abs(score_a - score_b) < ans)
			ans = abs(score_a - score_b);
		return;
	}

	// teamA
	if (cnt_a < n / 2){
		teamA[cnt_a] = num;
		dfs(num + 1, cnt_a + 1, cnt_b);
	}
	// teamB
	if (cnt_b < n / 2){
		teamB[cnt_b] = num;
		dfs(num + 1, cnt_a, cnt_b + 1);
	}
}

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> s[i][j];

	dfs(1, 0, 0);
	cout << ans << "\n";
	return 0;
}

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

int n, map[101][101], dist[101][101], ans = 987654321;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };
queue<pair<int, int> > q;

void dfs(int r, int c, int cnt){
	dist[r][c] = 1;
	map[r][c] = cnt;
	q.push(make_pair(r, c));

	for (int k = 0; k < 4; k++){
		int nr = r + dr[k];
		int nc = c + dc[k];

		if (0 <= nr && nr < n && 0 <= nc && nc < n && dist[nr][nc] == 0 && map[nr][nc] == 1){
			dfs(nr, nc, cnt);
		}
	}
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	int cnt = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (dist[i][j] == 0 && map[i][j] == 1)
				dfs(i, j, cnt++);

	while (!q.empty()){
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < n){
				if (map[nr][nc] == 0){
					q.push(make_pair(nr, nc));
					map[nr][nc] = map[r][c];
					dist[nr][nc] = dist[r][c] + 1;
				}
				else if (map[nr][nc] != map[r][c] && dist[r][c] + dist[nr][nc] - 2 < ans){
					ans = dist[r][c] + dist[nr][nc] - 2;
				}
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

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

int n, m, ans;
char map[101][101];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

int main(void){
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		cin >> map[i];
	}

	queue<pair<pair<int, int>, int> *gt; q;
	q.push(make_pair(make_pair(0, 0), 1));
	map[0][0] = '0';

	while (!q.empty()){
		int r = q.front().first.first;
		int c = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (r == n - 1 && c == m - 1){
			ans = cnt;
			break;
		}

		for (int k = 0; k < 4; k++){
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (0 <= nr && nr < n && 0 <= nc && nc < m && map[nr][nc] == '1'){
				q.push(make_pair(make_pair(nr, nc), cnt + 1));
				map[nr][nc] = '0';
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

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

int m, n, cnt = 0, day = -1, map[1001][1001];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

int main(void){
	freopen("text.txt", "r", stdin);
	cin >> m >> n;
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> map[i][j];
			if (map[i][j] == 0){
				cnt++;
			}
			else if (map[i][j] == 1){
				q.push(make_pair(i, j));
			}
		}
	}

	int size = q.size();
	while (!q.empty()){
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		size--;

		for (int i = 0; i < 4; i++){
			int nr = r + dr[i];
			int nc = c + dc[i];

			if (0 <= nr && nr < n && 0 <= nc && nc < m && map[nr][nc] == 0){
				q.push(make_pair(nr, nc));
				map[nr][nc] = 1;
				cnt--;
			}
		}

		if (size == 0){
			day++;
			size = q.size();
		}
	}

	if (cnt == 0)
		cout << day << "\n";
	else
		cout << -1 << "\n";
}

#include<iostream>
using namespace std;

int t, w, h, map[51][51], ans;
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

void dfs(int r, int c){
	map[r][c] = 0;

	for (int k = 0; k < 8; k++){
		int nr = r + dx[k];
		int nc = c + dy[k];

		if (0 <= nr && nr < h && 0 <= nc && nc < w && map[nr][nc]){
			dfs(nr, nc);
		}
	}
}

int main(void){
	while (cin >> w >> h && w !=0 && h != 0){
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				cin >> map[i][j];
			}
		}
		ans = 0;
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				if (map[i][j]){
					ans++;
					dfs(i, j);
				}
			}
		}
		cout << ans << "\n";
	}
}

#include<iostream>
using namespace std;

int n, l, map[2][101][101], check[2][101][101], ans = 0;

int main(void){
	cin >> n >> l;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cin >> map[0][i][j];
			map[1][j][i] = map[0][i][j];
		}
	}
	
	for (int i = 0; i < 2; i++){
		for (int j = 0; j < n; j++){
			int k = 0;
			for (; k < n - 1; k++){
				if (map[i][j][k] == map[i][j][k + 1]) continue;
				else if (map[i][j][k] + 1 == map[i][j][k + 1]){
					if (k + 1 - l >= 0){
						int m = k + 1 - l;
						if (m == k)
							if (check[i][j][m])
								break;
						for (; m < k; m++){
							if (map[i][j][m] != map[i][j][m + 1] || check[i][j][m] || check[i][j][m + 1]){
								break;
							}
						}
						if (m == k){
							for (int a = k + 1 - l; a < k + 1; a++){
								check[i][j][a] = true;
							}
							continue;
						}
						else break;
					}
					else break;
				}
				else if (map[i][j][k] - 1 == map[i][j][k + 1]){
					if (k + l < n){
						int m = k + 1;
						if (m == k + l)
							if (check[i][j][m])
								break;
						for (; m < k + l; m++){
							if (map[i][j][m] != map[i][j][m + 1] || check[i][j][m] || check[i][j][m + 1]){
								break;
							}
						}
						if (m == k + l){
							for (int a = k + 1; a < k + l + 1; a++){
								check[i][j][a] = true;
							}
							continue;
						}
						else break;
					}
					else break;
				}
				else break;
			}
			
			if (k == n - 1)
				ans++;
		}
	}
	cout << ans << "\n";
}

#include<stdio.h>

int main(void){
	int input[100][100], i, j, n, l, arr[200][100], mark[100] = { 0 }, k, ans = 0, flag;
	scanf("%d %d", &n, &l);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			scanf("%d", &input[i][j]);
			arr[i][j] = input[i][j];
		}
	}

	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			arr[i + n][j] = input[j][i];
		}
	}

	for (int i = 0; i < 2 * n; i++){
		flag = 1;
		for (int j = 0; j < n; j++)
			mark[j] = 0;

		for (int j = 0; j < n - 1 && flag; j++){
			if (arr[i][j] == arr[i][j + 1] + 1){ //left higher
				for (int k = 1; k <= l; k++){
					if (mark[j + k] == 1 || j + l >= n || arr[i][j + k] != arr[i][j + 1]){
						flag = 0;
						break;
					}
					mark[j + k] = 1;
				}
			}
			else if (arr[i][j] + 1 == arr[i][j + 1]){
				for (int k = 0; k < l; k++){
					if (mark[j - k] == 1 || j - l < -1 || arr[i][j - k] != arr[i][j]){
						flag = 0;
						break;
					}
					mark[j - k] = 1;
				}
			}
			else if (arr[i][j] == arr[i][j + 1])
				continue;
			else{
				flag = 0;
				break;
			}
		}
		if (flag == 1)
			ans++;
	}
	printf("%d\n", ans);
}

#include <stdio.h>
 
int n, l, a[101][101], dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 }, ans;
 
int main() {
    scanf("%d%d", &n, &l);
    int i, j;
    for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &a[i][j]);
    for (i = 0; i < n; i++) {
        int cnt = 1;
        for (j = 0; j < n - 1; j++) {
            if (a[i][j] == a[i][j + 1]) cnt++;
            else if (a[i][j] + 1 == a[i][j + 1] && cnt >= l) cnt = 1;
            else if (a[i][j] - 1 == a[i][j + 1] && cnt >= 0) cnt = -l + 1;
            else break;
        }
        if (j == n - 1 && cnt >= 0) ans++;
        cnt = 1;
        for (j = 0; j < n - 1; j++) {
            if (a[j][i] == a[j + 1][i]) cnt++;
            else if (a[j][i] + 1 == a[j + 1][i] && cnt >= l) cnt = 1;
            else if (a[j][i] - 1 == a[j + 1][i] && cnt >= 0) cnt = -l + 1;
            else break;
        }
        if (j == n - 1 && cnt >= 0) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

#include<iostream>
using namespace std;

int t;

int main(void){
	cin >> t;
	while (t--){
		int n, student[100001], finish[100001], ans = 0;
		bool check[100001];

		cin >> n;
		for (int i = 1; i <= n; i++){
			check[i] = false;
			finish[i] = 0;
		}

		for (int i = 1; i <= n; i++){
			cin >> student[i];
			finish[student[i]]++;
		}

		for (int i = 1; i <= n; i++){
			int now = i;
			while (!check[now] && !finish[now]){
				ans++;
				check[now] = true;
				finish[student[now]]--;
				now = student[now];
			}
		}

		cout << ans << "\n";
	}
	return 0;
}

#include<iostream>
using namespace std;

int t, n, student[100001], stack[100001], check[100001], ans = 0;

void dfs(int now, int cnt){
	check[now]++;
	stack[cnt] = now;

	if (check[student[now]] == 0){
		dfs(student[now], cnt + 1);
	}
	else if (check[student[now]] == 1){
		bool iscycle = false;
		for (int i = 1; i <= cnt; i++){
			if (stack[i] == student[now]){
				for (int j = i; j <= cnt; j++){
					check[stack[j]]++;
				}
				ans += i - 1;
				iscycle = true;
				break;
			}
		}
		if (!iscycle)
			ans += cnt;
	}
	else{ // check[student[now]] == 2
		ans += cnt;
	}
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		ans = 0;
		for (int i = 1; i <= n; i++){
			cin >> student[i];
			check[i] = 0;
		}

		for (int i = 1; i <= n; i++){
			if (check[i] == 0){
				dfs(i, 1);
			}
		}

		cout << ans << "\n";
	}
	return 0;
}

#include <iostream>
using namespace std;
int t, n, student[100010], check[100010], team, cnt;

void dfs(int now, int start){
	if (check[now] > 0)
		return;

	check[now] = ++cnt;

	if (check[student[now]] >= check[start])
		team += cnt - check[student[now]] + 1;
	else
		dfs(student[now], start);
}

int main(void){
	freopen("text.txt", "r", stdin);
	cin >> t;
	while (t--){
		cin >> n;
		cnt = team = 0;
		for (int i = 1; i <= n; i++){
			check[i] = 0;
			cin >> student[i];
		}
		for (int i = 1; i <= n; i++)
			dfs(i, i);
		cout << n - team << "\n";
	}
	return 0;
}