급하게임개발

https://www.acmicpc.net/problem/1941

이 문제는 처음 보고 어떻게 풀어야지라는 생각이 너무들었다 골드 3부터는 여러알고리즘이 섞여 어떻게 딱풀어야지라고 생각이 안나는 거같다

이 문제는 일단 조합으로 우리는 2차원 배열에서 원소를 뽑아줄것이다 원소를 뽑을 때는 1차원 배열이라고 생각해서 뽑아야한다

즉 위표와 같이 0,0 은 0번 0,1은 1번 이라고 생각해야한다 이거를 구하는 방법은 다음과 같다
행/5 + 열%5 를 하면 몇번짼지 우리는 알수 있다 이를 바탕으로 우리는 일차원 배열에서 7개를 뽑은 후 해당 7개의 원소가 서로 이어져 있고 S의 갯수가 4보다 많은지만 검사하면 된다

검사는 우리가 조합으로 뽑은 7개의 원소를 bfs 로 검사한다 즉 bfs로 특정 방향들을 탐색 한다 만약 끊어져있는 부분이 생기면큐에 원소가 들어가지 않을 테니 연속되지 않음을 우리는 알수 있다 전체 코드는 아래와 같다

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

char grid[5][5];
int ans = 0;
bool isConnected(vector<int> selected) {
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    int cnt = 1;
    bool isVisited[25] = { false, };
    bool sel[25] = { false, };

    for (int i = 0; i < 7; i++) {
        sel[selected[i]] = true;
    }

    queue<int> bfsQ;
    bfsQ.push(selected[0]);
    isVisited[selected[0]] = true;

    while (!bfsQ.empty()) {
        int cur = bfsQ.front();

        int r = cur / 5;
        int c = cur % 5;

        bfsQ.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];
            if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5)
                continue;
            int nxt = nr * 5 + nc;


            if (!isVisited[nxt] && sel[nxt]) {
                isVisited[nxt] = true;
                bfsQ.push(nxt);
                cnt++;
            }
        }
    }

    return cnt == 7;
}
void dfs(int start, int count, int sCount, vector<int> selected) {
    if (count == 7) {
        if (sCount >= 4 && isConnected(selected)) {
            ans += 1;
        }
        return;
    }
    if (sCount + (7 - count) < 4)
        return;

    for (int i = start; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;

        selected.push_back(i);

        if (grid[r][c] == 'S') {
            dfs(i + 1, count + 1, sCount + 1, selected);
        }
        else {
            dfs(i + 1, count + 1, sCount , selected);
        }

        selected.pop_back();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 5x5 격자 입력 받기
    for (int i = 0; i < 5; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < 5; j++) {
            grid[i][j] = line[j];
        }
    }

    vector<int> selected;
    dfs(0, 0, 0, selected);
    cout << ans << "\n";

    return 0;
}

https://www.acmicpc.net/problem/16947

이 문제도 어느 게임회사 코테에 나왔던 문제였다 코테풀기전에 이문제를 풀었다면 좋았었을텐데 지금에서야 접했다

이문제는 사이클이 하나만 있다고 가정하고 그래프릍 탐색해서 순환 구조를 파악하는 문제이다 
첫 번째로 사이클을 탐색하는 규칙은 자신으로 왔을떄 자신의 이전 노드들을 저장하고 있는다 그리고 만약에 다음노드를 방문했을때 이노드가 방문되어있고 이노드에 저장되어있던 노드가 지금 노드와 다르다면 이노드는 순환구조를 만든 노드라고 파악한다

이에 대한 코드는 아래와 같다

void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}

이렇게 dfs를 통해 방문 한 노드에 대해서 이전노드들을 검사해준다 그후 순환 노드가 파악이되었으면 pre 배열을 통해 이전 노드들을 파악해서 cycle로 체크를 해준다


이제 cycle로부터 각 노드들이 얼만큼 떨어져 있는 지 계산한다

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}

bfs를 통해 판별한다

전체 코드는 아래와같다

#include <iostream>
#include <vector>
#include <queue>
#include<cstring>
using namespace std;
bool isVisited[3001];
int pre[3001];
bool cycle[3001];
int dist[3001];
vector<int> vertex[3001];
int n;
bool hasCycle;

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}
void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}
int main() {
	cin >> n;
	int tmp1, tmp2;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2;
		vertex[tmp1].push_back(tmp2);
		vertex[tmp2].push_back(tmp1);
	}
	findCycle(1);
	memset(isVisited, false, 3001);
	bfs();
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << ' ';
	}
}

https://www.acmicpc.net/problem/16724

이 문제는 dfs를 통한 사이클을  검사한다 즉 dfs로 진행하면서 마무리전에는 진행 중으로 체크하다가 탐색하다가 진행중을 만나면 해당 영역은 사이클을 형성 한다 우리는 사이클의 갯수를 구해주면 된다

#include <iostream>

using namespace std;
const int MAX = 1000;

char arr[MAX][MAX];

int n, m;

int isVisited[MAX][MAX] = { 0, };

int dX[128]; int dY[128];
int cnt=0;
void dfs(int x, int y) {
	isVisited[x][y] = 1;
	int nx, ny;
	nx = x + dX[arr[x][y]];
	ny = y + dY[arr[x][y]];
	
	if (isVisited[nx][ny] == 0) {
		dfs(nx, ny);
	}
	else if (isVisited[nx][ny] == 1){
		cnt++;
	}
	isVisited[x][y] = 2;
}

int main() {
	cin >> n >> m;
	dX['U'] = -1; dY['U'] = 0;
	dX['D'] = 1; dY['D'] = 0;
	dX['R'] = 0; dY['R'] = 1;
	dX['L'] = 0; dY['L'] = -1;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (isVisited[i][j] == 0) {
				dfs(i, j);
			}
		}
	}

	cout << cnt;
}

https://www.acmicpc.net/problem/17135

이 문제는 그냥 여러개 섞어놓은 문제이다 병사를 배정하는것은 조합으로 dfs로 풀면 되고 
병사들이 몬스터를 잡는건 bfs로 풀면된다 조합에대한 모든것을 bfs함으로 브루트포스이기도 하다 사실이문제는 단지 기본적인 알고리즘 여러개를 섞어놓은것이다
주의할 점은 bfs를 할때

int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};

이 순서대로 해야한다 bfs가 거리가 가까운거는 보장하지만 왼쪽 탐색을 하기위해서는 해당 인덱스를 따라 해야지 왼쪽부터 탐색한다
또한 탐색하자마자 바로 0으로 바꾸지말고 중복으로 한 몬스터를 때릴수 있으므로 4로 체크하고 이후에 0으로 바꾼다

#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
int originArr[16][15];
int copyArr[16][15];
int N, M, D;
int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};
int maxNum;
bool isVisited[16][15] = { 0, };
bool AllDie() {
	bool isDie = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copyArr[i][j] == 1)
				isDie = false;
		}
	}
	return isDie;
}
void CopyOrigin() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = originArr[i][j];
		}
	}
}
bool CanGo(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M ) {
		return true;
	}
	else {
		return false;
	}
}
void downEnemy() {
	for (int i = N-1 ; i > 0; i--) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = copyArr[i - 1][j];
			if (copyArr[i][j] == 4)
				copyArr[i][j] = 0;
		}
	}
	for (int i = 0; i < M; i++) {
		copyArr[0][i] = 0;
	}
}
int bfs(int armyX, int armyY) {
	queue<pair<int, pair<int, int>>> ArmyQ;
	ArmyQ.push({ 0,{armyX,armyY} });
	int count = 0;
	while (!ArmyQ.empty()) {
		int curX = ArmyQ.front().second.first;
		int curY = ArmyQ.front().second.second;
		int cost = ArmyQ.front().first;
		ArmyQ.pop();
		if (cost > D)
			break;
		if (copyArr[curX][curY] == 4) {
			break;
		}
		if (copyArr[curX][curY] == 1) {
			copyArr[curX][curY] = 4;
			count += 1;
			break;
		}

		for (int i = 0; i < 3; i++) {
			int nextX = curX + goX[i];
			int nextY = curY + goY[i];
			if (CanGo(nextX, nextY)) {
				ArmyQ.push({ cost + 1,{nextX,nextY} });
			}
		}
	}
	return count;
}
void dfs(int start, int count) {
	if (count == 3) {// 병사를 3명 다배치 했을 경우
		CopyOrigin();
		int num = 0;
		while (!AllDie()) {
			for (int i = 0; i < M; i++) {
				if (copyArr[N][i] == 3) {
					num += bfs(N, i);
				}
			}
			downEnemy();
		}
		maxNum = max(num, maxNum);
	}
	
	else {
		for (int i = start+1; i < M; i++) {
			originArr[N][i] = 3;
			dfs(i, count + 1);
			originArr[N][i] = 2;
		}
	}
}
int main() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> originArr[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 2;
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 3;
		dfs(i, 1);
		originArr[N][i] = 2;
	}
	cout << maxNum;
}

https://www.acmicpc.net/problem/3109

이 문제는 그리드를 이용한 dfs이다 즉 dfs의 탐색방향을 그리디를 통해 정해주게 되는것이다 우리는 오른쪽 부터 왼쪽으로 파이프를 순서대로 연결할건데 이때 파이프는 오른쪽 ,오른쪽 아래 ,왼쪽 아래 이렇게 만 움직일수있는데 우리가 오른쪽부터 파이프를 놓는데 진행중에 왼쪽 방향으로 탐색을 진행하게되면 파이프가 쭉 왼쪽으로 가면서 다른애들의 연결을 막게된다 왼쪽부터 탐색할거면 반대로 놓아도 되긴 한다

#include<iostream>
using namespace std;
int R, C;
int arr[10001][501];
int cnt = 0;
int dr[3] = { -1, 0, 1 };
int dc[3] = { 1, 1, 1 };
bool canGo(int r, int c) {
	if (!arr[r][c] && r >= 0 && r < R && c >= 0 && c < C)
		return true;
	else
		return false;
}
bool dfs(int r, int c) {
	if (c== C - 1) {
		cnt += 1;
		return true;
	}
	else {
		arr[r][c] = 1;
		for (int i = 0; i < 3; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (canGo(nr, nc)) {
				if (dfs(nr, nc)) {
					return true;
				}
			}
		}
		return false;
	}
}
int main() {
	cin >> R >> C;
	string inputStr;
	for (int i = 0; i < R; i++) {
		cin >> inputStr;
		for (int j = 0; j < C; j++) {
			if (inputStr[j] == '.')
				arr[i][j] = 0;
			else
				arr[i][j] = 1;
		}
	}

	for (int i = 0; i < R; i++) {
		dfs(i, 0);
	}

	cout << cnt;
	return 0;
}

https://www.acmicpc.net/problem/1038

이 문제의 경우 문제 분류에 부르트 포스 라고 되어있지만 정확히는 dfs 백트래킹이라고 보는게 맞을거 같다 
처음에는 0 부터 9876543210 까지 수들을 검사해서 해당 수가 감소하는 수 인지를 검사하는 방법을 사용했지만 해당 방법은 시간초과를 유발했기에 dfs와 백트래킹을 사용하여 해당 문제를 풀었다

해당 이미지를 보자 우리가 백트래킹으로감소하는 수를 만들려고 할시 반복문의 범위를 단지 이전 자리의 숫자의 값까지만 증가시켜주면서 넣어주면 된다

#include <iostream>
using namespace std;
long  long arr[1000001];
long  long n;
long  long numCnt;
long  long idxOfNum = 10;
void makeDecreaseNum(long  long num , long  long numOfone , long  long cntOfNum) {
	if (cntOfNum==numCnt) {
		arr[idxOfNum] = num;
		idxOfNum++;
	}
	else {
		num = num * 10;
		for (long  long i = 0; i < numOfone; i++) {
			makeDecreaseNum(num + i, i, cntOfNum+1);
		
		}
	}

}
int main() {
	cin >> n;
	for (long  long i = 0; i < 1000001; i++) {
		arr[i] = -1;
	}
	for (long  long i = 0; i < 10; i++) {
		arr[i] = i;
	}
	for (long  long i = 2; i <= 11; i++) {
		numCnt = i;
		for (long  long j = 1; j <= 9; j++) {
			makeDecreaseNum(j, j, 1);
		}
	}
	cout << arr[n];
}

https://www.acmicpc.net/problem/1520

이 문제는 처음에 dfs로 만 풀었으나 시간초과 가 났다 이에 dp와 섞어서 풀어야 한다는 힌트를 보게 되었다

			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);

dp의 점화식은 이와 같은데 그이유는 나는 내가 다음에 갈수 있는 경로들이 갈수 있는 경로들의 합으로 표현할수 있기 때문이다

나는 dp배열을 -1로초기화를 해주었는데 그이유는 방문하지 않았다는 표시를 -1로 하게되었습니다 0은 방문은 했으나 해당 영역을 통해서 경로를 찾을 수 없는 것이라고 결정 하였습니다. 경로를 탐색하러 들어갔을 때 이미 해당 노드를 방문 한적이 있으면 해당 노드를 통해서 방문했던 길의 갯수가 해당 노드의 저장이 되어있기에 해당 노드의 값을 그대로 반환해주었습니다.

#include <iostream>
#include <set>
using namespace std;
int arr[500][500];
int dp[500][500];
int m, n;
int cnt;
int xidx[4] = { 1,0,-1,0 };
int yidx[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int height) {
	if (x >= 0 && x < m && y>=0 && y < n && height > arr[x][y])
		return true;
	else
		return false;
}

int dfs(int x,int y) {
	if (x == m - 1 && y == n - 1) {
		return 1;
	}
	if (dp[x][y] != -1)
	{
		return dp[x][y];
	}

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (canGo(x + xidx[i], y + yidx[i], arr[x][y])) {
			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);
		}
	}
	return dp[x][y];
}
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
}

전체 로직은 위와 같다

https://www.acmicpc.net/problem/14500

이 문제의  경우 나는 일단 dfs와 ㅗ 모양의 블록을 나눠서 풀었다 .

테트로미노에는 이렇게 현재 블럭이 있는데

빨간색을 제외한 블록들은 dfs로 검색하면 회전까지 나오는 모양 들이다 빨간색으로 둘러싼 모형들을 배열에다 다 넣어서 최대값을 구하는게 해당 문젠데 그후 빨간색으로 둘러친걸 넣어보면서 최대값을 구하면 된다

일단 빨간색을 제외한 코드의 부분은

void dfs(int x, int y, int cnt , int sum) {
	if (cnt == 4) {
		if (sum > maxNum) {
			maxNum = sum;
		}
	}
	else {
		if (canGo(x + 1, y)) {
			isVisited[x + 1][y] = true;
			dfs(x + 1, y, cnt + 1, sum + arr[x+1][y]);
			isVisited[x + 1][y] = false;
		}
		if (canGo(x - 1, y)) {
			isVisited[x - 1][y] = true;
			dfs(x - 1, y, cnt + 1, sum + arr[x-1][y]);
			isVisited[x - 1][y] = false;
		}
		if (canGo(x , y+1)) {
			isVisited[x][y+1] = true;
			dfs(x , y+1, cnt + 1, sum + arr[x][y+1]);
			isVisited[x][y + 1] = false;
		}
		if (canGo(x , y-1)) {
			isVisited[x ][y-1] = true;
			dfs(x , y-1, cnt + 1, sum + arr[x][y-1]);
			isVisited[x][y - 1] = false;
		}
	}
}

이렇게 된다 그이이유는 저위에 빨간색을 제외한 부분들을 회전과 대칭을 고려할경우 dfs로 나오는 모형과 똑같기 떄문이다
그후 빨간색으로 둘러쳐진 모양은 노가다를 했다

void mountatinShape(int startX, int startY) {
	if (canGo(startX + 1, startY) && canGo(startX, startY - 1) && canGo(startX,startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}

	if (canGo(startX + 1, startY) && canGo(startX -1, startY) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX-1][startY] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX + 1, startY) && canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
}

그래서 이두 로직을 합치면서 최댓값을 저장해주면 이문제는 해결이다

#include<iostream>
using namespace std;
int n, m;
int arr[500][500];
bool isVisited[500][500] = { 0, };
int maxNum = 0;
//세로 1자
bool canGo(int px, int py) {
	if (px >= 0 && px < n && py >= 0 && py < m && !isVisited[px][py]) {
		return true;
	}
	else
		return false;
}
void dfs(int x, int y, int cnt , int sum) {
	if (cnt == 4) {
		if (sum > maxNum) {
			maxNum = sum;
		}
	}
	else {
		if (canGo(x + 1, y)) {
			isVisited[x + 1][y] = true;
			dfs(x + 1, y, cnt + 1, sum + arr[x+1][y]);
			isVisited[x + 1][y] = false;
		}
		if (canGo(x - 1, y)) {
			isVisited[x - 1][y] = true;
			dfs(x - 1, y, cnt + 1, sum + arr[x-1][y]);
			isVisited[x - 1][y] = false;
		}
		if (canGo(x , y+1)) {
			isVisited[x][y+1] = true;
			dfs(x , y+1, cnt + 1, sum + arr[x][y+1]);
			isVisited[x][y + 1] = false;
		}
		if (canGo(x , y-1)) {
			isVisited[x ][y-1] = true;
			dfs(x , y-1, cnt + 1, sum + arr[x][y-1]);
			isVisited[x][y - 1] = false;
		}
	}
}

void mountatinShape(int startX, int startY) {
	if (canGo(startX + 1, startY) && canGo(startX, startY - 1) && canGo(startX,startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}

	if (canGo(startX + 1, startY) && canGo(startX -1, startY) && canGo(startX, startY + 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX-1][startY] + arr[startX][startY + 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
	if (canGo(startX + 1, startY) && canGo(startX - 1, startY) && canGo(startX, startY - 1) && canGo(startX, startY)) {
		int sum = 0;
		sum = arr[startX + 1][startY] + arr[startX - 1][startY] + arr[startX][startY - 1] + arr[startX][startY];
		if (sum > maxNum)
			maxNum = sum;
	}
}
void tet1(int startX, int startY) {
	isVisited[startX][startY] = true;
	dfs(startX, startY, 1,arr[startX][startY]);
	isVisited[startX][startY] = false;

}

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			mountatinShape(i, j);
			tet1(i, j);
		}
	}

	cout << maxNum;
}