Untitled

https://send.zcyph.cc/download/8fd9d1ab3d067e65/#CGbziVgwx4-bPhl19Qb4EA

/// Hugo Fire
#include <stdio.h>

#define MAX_SIZE 20
#define MAX_INT 1000000000

int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int diamond[MAX_SIZE][MAX_SIZE];
bool exit[MAX_SIZE][MAX_SIZE];
bool lake[MAX_SIZE][MAX_SIZE];
int fire[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int Q[MAX_SIZE * MAX_SIZE];
int front, rear;
int N, M, maxDiamond;

void spreadFire()
{
	int r, c, nextR, nextC;
	while (front <= rear) {
		r = Q[front] / MAX_SIZE;
		c = Q[front++] % MAX_SIZE;
		for (int d = 0; d < 4; d++) {
			nextR = r + dy[d];
			nextC = c + dx[d];
			if (nextR < 1 || nextR > N || nextC < 1 || nextC > M)
				continue;
			if (fire[nextR][nextC] > fire[r][c] + 1 && !lake[nextR][nextC]) {
				fire[nextR][nextC] = fire[r][c] + 1;
				Q[++rear] = nextR * MAX_SIZE + nextC;
			}
		}
	}
}

void go(int r, int c, int time, int collected)
{
	if (exit[r][c]) {//exit
		if (collected > maxDiamond)
			maxDiamond = collected;
	}

	for (int d = 0; d < 4; d++) {
			int nextR = r + dy[d];
			int nextC = c + dx[d];
			if (nextR < 1 || nextR > N || nextC < 1 || nextC > M || visited[nextR][nextC])
				continue;
			int nextTime = lake[nextR][nextC] ? time + 2 : time + 1;
			if (nextTime < fire[nextR][nextC]) {
				visited[nextR][nextC] = true;
				go(nextR, nextC, nextTime, collected + diamond[nextR][nextC]);
				visited[nextR][nextC] = false;
			}
	}
}


int main()
{	
	int T, tc;
	int sR, sC;
	int tmpR, tmpC;
	int lakeCnt, exitCnt, fireCnt;

	scanf("%d", &T);
	for (tc = 1; tc <= T; tc++) {
		rear = -1;
		front = 0;
		scanf("%d%d%d%d", &N, &M, &sR, &sC);

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++) {
				fire[i][j] = MAX_INT;
				lake[i][j] = exit[i][j] = visited[i][j] = false;
			}

		scanf("%d", &fireCnt);		
		for (int i = 0; i < fireCnt; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			fire[tmpR][tmpC] = 0;
			Q[++rear] = tmpR * MAX_SIZE + tmpC;
		}

		scanf("%d", &lakeCnt);		
		for (int i = 0; i < lakeCnt; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			lake[tmpR][tmpC] = true;
		}

		scanf("%d", &exitCnt);		
		for (int i = 0; i < exitCnt; i++) {
			scanf("%d%d", &tmpR, &tmpC);
			exit[tmpR][tmpC] = true;
		}

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= M; j++)
				scanf("%d", &diamond[i][j]);

		maxDiamond = -1;
		spreadFire();	
		visited[sR][sC] = true;

		go (sR, sC, 0, diamond[sR][sC]);

		printf("Case #%d\n%d\n", tc, maxDiamond);	
	}

	return 0;
}

// quan tuong
#include<iostream>

using namespace std;
int	n,m,p,q,s,t;
int dx[4] = {-1,-1,1,1};
int dy[4] = {-1,1,1,-1};

int arr[205][205];

#define MAXQ 1000000

int Q[MAXQ];
int bot , top;


void reset(){
	top = -1;
	bot = -1;
}

bool isEmpty(){
	return top == bot;
}

void push( int value){
	bot++;
	Q[bot] = value;
}

int pop(){
	top++;
	return Q[top];
}



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

void BFS(int x , int y){
	reset();
	push(x);
	push(y);
	
	while (!isEmpty())
	{
		int a = pop();
		int b = pop();
		for( int k =0 ; k < 4 ; k++){
			int xx = a + dx[k];
			int yy = b + dy[k];
			while (xx > 0 && xx <= n &&  yy > 0 && yy <= n && arr[xx][yy] != -1)
			{
				if(arr[xx][yy] == 0){
					arr[xx][yy] = arr[a][b] + 1;
					if(xx == s && yy == t) break;
					push(xx);
					push(yy);
				}
				xx = xx + dx[k];
				yy = yy + dy[k];
			}
		}
	}
}



int main(){
//	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for( int tc = 1 ; tc <= T; tc++){

		cin >> n >> m >> p >> q >> s >> t;


		reset_arr();

		arr[p][q] = 1;

		for( int i = 0 ; i < m ; i++){
			int x , y;
			cin >> x >> y;
			arr[x][y] = -1;
		}

		BFS(p,q);

		if(arr[s][t] == 0){
			cout << -1 << endl;
		}else
		{
			cout << arr[s][t] - 1 << endl;
		}

	}

	return 0;
}
// crazy king
#include <iostream>
#define MAX_N 105
#define INF 1000000
using namespace std;

int map[MAX_N][MAX_N];

int N, M;
int Q[MAX_N * MAX_N];
int front, rear;

int dy[] = {0, 1, 0, -1, -1, -1, 1, 1};
int dx[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dy1[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dx1[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int eR, eC;

void bfs(int r, int c)
{
	Q[0] = r * MAX_N + c;
	front = rear = 0;
	int nR, nC;
	while (front <= rear) {
		r = Q[front] / MAX_N;
		c = Q[front++] % MAX_N;
		for (int d = 0; d < 8; d++) {
			nR = r + dy[d];
			nC = c + dx[d];
			if (nR < 0 || nR >= N || nC < 0 || nC >= M) 
				continue;
			if (nR == eR && nC == eC) {
				map[nR][nC] = map[r][c] + 1;
				return;
			}
			
			if (map[nR][nC] > map[r][c] + 1) {
				map[nR][nC] = map[r][c] + 1;
				Q[++rear] = nR * MAX_N + nC;
			}			
		}
	}
}

int main(void)
{
	int test_case;
	int T;
	char tmp;

	cin >> T;
	int sR, sC;
	for (test_case = 0; test_case < T; ++test_case)
	{
		cin>>M>>N;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++) 
				map[i][j] = INF;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {			
				cin >> tmp;
				switch (tmp)
				{
				case 'Z':
					map[i][j] = -1;
					for (int d = 0; d < 8; d++) {
						int xx = i + dy1[d];
						int yy = j + dx1[d];
						if(xx >= 0 && xx < N && yy >= 0 && yy < M && map[xx][yy] == INF)
							map[xx][yy] = -1;
					}
					break;
				case 'A':
					sR = i;
					sC = j;
					map[i][j] = 0;
					break;
				case 'B':
					eR = i;
					eC = j;
					break;
				default:
					break;
				}
			}
		}

		bfs(sR, sC);
        
		int Answer = map[eR][eC] == 1000000? -1 : map[eR][eC];
		cout<<Answer<<endl;
	}
	return 0; 
}

//// sea water
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int n, m;
int map[102][102];
int Hmax=0;
int Hmin = 0;
void read ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin>>map[i][j];
			Hmax = max (map[i][j] , Hmax);
			if ((i==1 || i==n || j==1 || j==m) && map[i][j]!=0 && map[i][j] < Hmin) Hmin = map[i][j];
		}
	}
}

int check[102][102];
int check_connect[102][102];
void init ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			check[i][j]=0;
			check_connect[i][j]=0;
		}
	}
}

int extra;
int x_ar[]={+1, +0, -1, +0};
int y_ar[]={+0, -1, +0, +1};
void Spread (int i, int j)
{
	check[i][j]=1;
	int X,Y;
	for (int k=0; k<4; k++)
	{
		 X=j+x_ar[k];
		 Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check[Y][X]==0 && map[Y][X]<=extra) Spread(Y, X);
		}
	}
}

void DFS (int i, int j)
{
	check_connect[i][j]=1;
	int X,Y;
	for (int k=0; k<4; k++)
	{
		 X=j+x_ar[k];
		 Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
		}
	}
}

int main ()
{
	freopen("input.txt", "r", stdin);
	int t=0;
	while (1)
	{
		cin>>n>>m;
		if (n==0 && m==0) break;
		t++;
		read ();
		int kt=0;
		for (int k=Hmin; k<=Hmax; k++)
		{
			extra=k;
			init ();
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if ((i==1 || i==n || j==1 || j==m) && map[i][j]<= extra && check[i][j]==0) Spread (i, j);
				}
			}

			//dem lien thong?
			int count_connect=0;
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if (check_connect[i][j]==0 && check[i][j]==0)
					{
						count_connect++;
						DFS (i, j);
					}
				}
			}
			if (count_connect>1)
			{
				kt=1;
				break;
			}
		}
		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
		else cout<<"Case "<<t<<": Island never splits."<<endl;
	}
	return 0;
}

/// dao cot
#include <iostream>
using namespace std;
int a[100][20];
int viscot[20];
int trangthai[20];
int n,m,k;
int kq;
int dem(){
	int dem=0;
	for(int i=0;i<n;i++){
		int sum=0;
		for(int j=0;j<m;j++){
			if((a[i][j]+trangthai[j])%2==0) break;
			else sum++;
		}
		if(sum==m) dem++;
	}
	return dem;
}
void backtrack(int x,int sum){
	if(kq==n) return;
	if(sum>k) return;
	if (x==m){
		if((k-sum)%2==0){
		if(kq<dem()) kq=dem();
		}
		return;
	}
	for(int i=0;i<2;i++){
		trangthai[x]=i;
		backtrack(x+1,sum+i);
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for(int tc=1; tc<=t;tc++){
		cin>>n>>m>>k;
		for(int i=0;i<n; i++){
			for(int j=0; j<m; j++){
				cin>>a[i][j];
			}
		}
		kq=0;
		backtrack(0,0);
		cout<<"Case #"<<tc<<" "<<kq<<endl;
	}
	return 0;
}