Untitled
unknown
plain_text
a year ago
141 kB
12
Indexable
#tancongthanhtri
#include<iostream>
using namespace std;
const int vc = 1000;
int t, m, i, u_i, c_i;
int visited[1001];
int aLk[1001][1001];
int aBD[1001];
int n, res;
bool isTrue;
void resetMang(){
for(int i=0; i<n; i++)
visited[i] =0;
}
void DFS(int tempThanh, int thanh, int sl, int tempMin, int d1, int d2){
if(tempThanh == thanh && sl>=3){
isTrue = true;
res+= tempMin;
aLk[d1][d2] = 0;
aLk[d2][d1] = 0;
return;
}
for(int i=0; i<n; i++){
if(isTrue) return;
if(aLk[tempThanh][i] == 1 && (!visited[i] || (i == thanh && sl>=3))){
visited[i] = 1;
int value = aBD[tempThanh] + aBD[i];
if(tempMin > value){
DFS(i, thanh, sl+1, value, tempThanh, i);
}else{
DFS(i, thanh, sl+1, tempMin, d1, d2);
}
}
}
}
void calc(){
for(int thanh = 0; thanh <n; thanh++){
resetMang();
visited[thanh] = 1;
isTrue = false;
DFS(thanh, thanh, 1, vc, -1, -1);
while(isTrue){
resetMang();
visited[thanh] = 1;
isTrue = false;
DFS(thanh, thanh, 1, vc, -1, -1);
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=0; tc<t; tc++){
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
aLk[i][j] = 0;
}
}
int thanh, soMayBD, soLk, tempThanh;
for(int i=0; i<n; i++){
cin>>thanh>>soMayBD>>soLk;
aBD[thanh] = soMayBD;
for(int j=0; j< soLk; j++){
cin>>tempThanh;
aLk[tempThanh][thanh] = 1;
aLk[thanh][tempThanh] = 1;
}
}
res = 0;
calc();
cout<<res<<endl;
}
return 0;
}
#sky map
#include <iostream>
using namespace std;
int tc, T, n, a[26][26], visited[26][26], num, cnt, max1;
int qX[1000], qY[1000], u, v, k, tx, ty, i, j;
int frontX, rearX, frontY, rearY;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void initQueue()
{
frontX = rearX = frontY = rearY = -1;
}
int isEmptyX()
{
if (frontX == rearX)
return 1;
return 0;
}
int isEmptyY()
{
if (frontY == rearY)
return 1;
return 0;
}
void enQueueX(int elementX)
{
rearX++;
qX[rearX] = elementX;
}
void enQueueY(int elementY)
{
rearY++;
qY[rearY] = elementY;
}
int deQueueX()
{
frontX++;
return qX[frontX];
}
int deQueueY()
{
frontY++;
return qY[frontY];
}
void BFS(int x, int y)
{
visited[x][y] = 1;
cnt = 1;
enQueueX(x);
enQueueY(y);
while(!isEmptyX()){
u = deQueueX();
v = deQueueY();
for(int k=0; k<4; k++){
tx = u + dx[k];
ty = v + dy[k];
if (tx >= 0 && tx < n && ty >= 0 && ty < n
&& !visited[tx][ty] && a[tx][ty] == 1){
enQueueX(tx);
enQueueY(ty);
visited[tx][ty] = 1;
cnt++;
}
}
}
}
void DFS(int x, int y){
visited[x][y] = 1;
cnt++;
int k;
for(k=0; k<4; k++){
tx = x + dx[k];
ty = y + dy[k];
if(tx>=0 && tx<n && ty>=0 &&ty <n && !visited[tx][ty] && a[tx][ty]){
DFS(tx, ty);
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
cin>>T;
for (tc = 0; tc < T; tc++)
{
cin>>n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
cin>>a[i][j];
visited[i][j] = 0;
}
num = max1 = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (a[i][j] == 1 && !visited[i][j])
{
num++;
cnt =0;
//initQueue();
//BFS(i, j);
DFS(i, j);
if (max1 < cnt)
max1 = cnt;
}
}
cout<<num<< " " <<max1<<endl;
}
return 0;
}
#lang mac
#include <iostream>
using namespace std;
int N;
int map[301][301];
int visited[301];
int visitEdge[301][301];
int so_vung, so_cau, so_vung_co_lap, so_canh;
void reset(){
for(int i = 0; i < N; i++) visited[i] = 0;
}
void Try(int u){
for( int i= 0; i < N; i++) {
if (map[u][i] == 1 && !visited[i]) {
visited[i] = 1;
Try(i);
}
}
}
void countArea(){
for ( int i = 0; i<N; i++) {
if(!visited[i]) {
so_vung++;
Try(i);
}
}
}
bool flag;
void checkBridge(int start, int end){
for(int i = 0; i < N; i++){
if(map[start][i] == 1 && visited[i] == 0){
if ( i == end) {
flag = false;
return;
}
visited[i] = 1;
checkBridge(i,end);
if(!flag) return;
}
}
}
int countBridges (){
int ans = 0;
for ( int i = 0; i< N; i++)
for ( int j = 0; j< N; j++)
visitEdge[i][j] = 0;
for(int r = 0; r < N; r++) {
for (int c = 0; c< N; c++) {
if(map[r][c] == 1 && visitEdge[r][c] == 0) {
map[r][c]= map[c][r] = 0;
visitEdge[r][c] = visitEdge[c][r] = 1;
flag = true;
reset();
checkBridge(r,c);
if (flag) ans++;
map[r][c]= map[c][r] = 1;
}
}
}
return ans;
}
int main(){
freopen("input.txt", "r", stdin);
int t; cin >> t;
for(int tc = 0; tc < t; tc++){
so_vung = 0;
so_cau = 0;
so_vung_co_lap = 0;
so_canh = 0;
cin >> N;
for(int i = 0; i < N; i++){
bool flag = true;
for(int j = 0; j< N; j++) {
cin>> map[i][j];
if (map[i][j] == 1) {
so_canh++;
flag = false;
}
}
if (flag) so_vung_co_lap++;
}
so_canh /= 2;
reset();
countArea();
if ((N > 2 && so_canh == (N*(N-1)/2)) || so_canh == 0) so_cau = 0;
else {
so_cau = countBridges();
}
cout << so_vung <<" "<< so_vung_co_lap <<" "<< so_cau << endl;
}
return 0;
}
#advertisement
#include <iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
/*
Tư tưởng là:
Tìm khoảng thời gian (bắt đầu có khách - khách cuối cùng rời khỏi)
Băm khoảng này thành các slots thời gian
Có 3 quảng cáo. Try từ quảng cáo 1
Mỗi quảng cáo có n khe lựa chọn
Cứ gắn quảng cáo vào rồi check. Khi gắn đủ 3 quảng cáo thì tìm điểm lớn nhất
*/
int N; // số khách hàng
int L[4]; // thời gian của mỗi quảng cáo
int P[4]; // điểm thưởng cho mỗi quảng cáo
int minT; // thời gian có khách hàng đầu tiên
int maxT; // thời gian có khách hàng cuối cùng
int adv[4][2]; // quảng cáo thời gian bắt đầu và thời gian kết thúc
int V[51][2]; // khách hàng truy cập và thời gian bắt đầu và kết thúc
int ans;
void reset() { // reset thời gian vào và thời gian kết thúc của quảng cáo
for (int i = 1; i <= 3; i++)
adv[i][0] = adv[i][1] = 0;
}
int TinhDiem() {
int point = 0;
for (int i = 1; i <= N; i++) {
int maxP = 0;
for (int j = 1; j <= 3; j++) {
if (adv[j][0] >= V[i][0] && adv[j][1] <= V[i][1])
if (P[j] > maxP)
maxP = P[j];
}
point += maxP;
}
return point;
}
int check(int k, int st_slot) {
for (int i = 1; i < k; i++) {
int ed_slot = st_slot + L[k]-1;
if (adv[i][0] <= st_slot && st_slot <= adv[i][1]) return 0; // đã có quảng cáo chứa st_slot
if (adv[i][0] <= ed_slot && ed_slot <= adv[i][1]) return 0; // đã có quảng cáo chứa ed_slot
if (st_slot <= adv[i][0] && adv[i][0] <= ed_slot) return 0; // khoảng slot chứa điểm đầu quảng cáo khác
if (st_slot <= adv[i][1] && adv[i][1] <= ed_slot) return 0; // khoảng slot chứa điểm cuối quảng cáo khác
}
return 1; // nếu là quảng cáo đàu tiên thì chắc chắn vứt vào được
}
void set(int k, int st_slot) { // điềm thời gian bắt đầu và kết thúc của quảng cáo
adv[k][0] = st_slot;
adv[k][1] = st_slot + L[k]-1;
}
void unset(int k, int st_slot) { // bỏ thời gian bắt đầu và kết thúc của quảng cáo
adv[k][0] = adv[k][1] = 0;
}
void backTrack(int k) {
if (k == 4) { // hết 3 quảng cáo thì tính điểm
int point = TinhDiem();
if (point > ans)
ans = point; // trả về điểm lớn nhất và thoát
return;
}
for (int i = minT; i <= maxT+1; i++) {
if (check(k, i)) {
set(k, i);
backTrack(k + 1);
unset(k, i);
}
}
}
int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N; // Nhập vào số khách hàng
cin >> L[1] >> L[2] >> L[3];
cin >> P[1] >> P[2] >> P[3];
minT = 100; maxT = -1;
int a, d;
for (int i = 1; i <= N; i++) {
cin >> a >> d;
V[i][0] = a;
V[i][1] = a + d-1;
if (V[i][1] > maxT) maxT = V[i][1];
if (V[i][0] < minT) minT = V[i][0];
}
reset();
ans = 0;
backTrack(1);
cout << "Case #" << tc << endl << ans << endl;
}
return 0;
}
#bong bay
#include<iostream>
// code 100
using namespace std;
int sobong;
int arr[10];
int visit[10];
int sumMax = 0;
int vitri;
int left(int i){
for(int j = i-1;j>=0;j--){
if(visit[j] ==1){
return j;
}
}
return -1;
}
int right(int i){
for(int j = i+1;j<sobong;j++){
if(visit[j] ==1){
return j;
}
}
return -1;
}
int point(int vt){
int l = left(vt);
int r = right(vt);
if(l != -1 && r != -1){
return arr[l]*arr[r];
}
if(l != -1 && r == -1){
return arr[l];
}
if(l == -1 && r != -1){
return arr[r];
}
return arr[vt];
}
void BT(int vt, int sum){
if(vt == sobong ){
sum+= arr[vitri];
if(sum > sumMax) sumMax = sum;
return;
}
for (int i = 0; i < sobong; i++)
{
if(visit[i]==1){
visit[i]=0;
if (vt==sobong - 1){
vitri = i;
BT(vt+1,sum);
} else
BT(vt+1,sum+point(i));
visit[i]=1;
}
}
}
int main()
{
int tc;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; tc++)
{
cin >> sobong;
for (int i = 0; i < sobong; i++)
{
cin >> arr[i];
visit[i] = 1;
}
sumMax = 0;
BT(0, 0);
cout << "#" << tc << " " << sumMax << endl;
}
return 0;
}
#connect processor
#include<iostream>
using namespace std;
// code 100/100
int tc,n;
int map[12][12], visited[12][12];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int chip[12][2], Minn=987654,TongChip=0,dai=0;
bool checkMap(int x, int y){
return (0<=x && x<n && 0<=y && y<n);
}
bool checkHuong (int x, int y, int hgx, int hgy){
int nx = x+hgx;
int ny = y+hgy;
while(checkMap(nx,ny)){
if(visited[nx][ny]==1){
return false;
}
nx += hgx;
ny += hgy;
}
return true;
}
void visit(int x, int y, int hgx, int hgy, int val){
int nx = x+hgx;
int ny = y+hgy;
dai=0;
while(checkMap(nx,ny) && map[nx][ny]==0){
dai++;
visited[nx][ny]+=val; // đánh dấu ô đã đi qua
nx += hgx;
ny += hgy;
}
}
void BT(int ch,int sum){ // chip, sum
if(sum>Minn) return;
if(ch==TongChip){
if(sum<Minn) Minn=sum;
return;
}
int x=chip[ch][0];
int y=chip[ch][1];
if(x==-1 && y==-1){ // chip(-1,-1) là ko thể nối nguồn
BT(ch+1,sum);
}
else{
for(int i=0;i<4;i++){
if(checkHuong(x,y,dx[i],dy[i]) ){
visit(x,y,dx[i],dy[i],1);
BT(ch+1,sum+dai);
visit(x,y,dx[i],dy[i],-1); // trả lại visit
}
}
return;
}
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>tc;
for(int t=1;t<=tc;t++){
cin>>n;
Minn=987654;
TongChip=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
visited[i][j]=0;
cin>>map[i][j];
if(map[i][j]==1){
visited[i][j]=1;
if(1<=i && i <= n-1 && 1<=j && j <= n-1){ // chỉ lưu các chip trong bo
chip[TongChip][0]=i;
chip[TongChip][1]=j;
TongChip++;
}
}
}
}
for(int i=0;i<TongChip;i++){ // check tất cả các chip
bool ch[4];
for(int j=0;j<4;j++){
ch[j]=checkHuong(chip[i][0],chip[i][1],dx[j],dy[j]);
}
if(!ch[0] && !ch[1] && !ch[2] && !ch[3] ){ // chip ko đi được hướng nào cả
chip[i][0]=-1;
chip[i][1]=-1;
}
}
BT(0,0);
cout<<"#"<<t<<" "<<Minn<<endl;
}
return 0;
}
#cover rectangle
#include <iostream>
using namespace std;
// code 100/100
int map[7][8];
int domino[7][7];
int visit[7][8];
int ans;
int dx[2] = {1,0};
int dy[2] = {0,1};
void Try(int k){
if (k == 56){
ans++;
return;
}
int x = k / 8;
int y = k % 8;
if (!visit[x][y]){
for (int d = 0; d < 2; d++){
int xx = x + dx[d];
int yy = y + dy[d];
if (xx>=0 && xx <7 && yy>=0 && yy<8 && !visit[xx][yy] && !domino[map[x][y]][map[xx][yy]]){
visit[x][y] = visit[xx][yy] = 1;
domino[map[x][y]][map[xx][yy]] = domino[map[xx][yy]][map[x][y]] = 1;
Try (k+1);
visit[x][y] = visit[xx][yy] = 0;
domino[map[x][y]][map[xx][yy]] = domino[map[xx][yy]][map[x][y]] = 0;
}
}
}
else Try(k+1);
}
int main(){
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for (int tC = 1; tC <= T; tC++){
for (int i = 0; i < 7; i++)
for (int j = 0; j < 8; j++){
cin >> map[i][j];
visit[i][j] = 0;
}
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
domino[i][j] = 0;
ans = 0;
Try(0);
cout << "#" << tC << " " << ans << endl;
}
return 0;
}
#fishing
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
// có 3 cổng. sắp xếp số người của mỗi cổng sao cho khoảng cách số người của cổng đó cách cổng đó ít nhất.
/* hướng giải bài toán :
nếu bên trái còn vị trí gần hơn thì đẩy hết vào trái, bên phải còn vị trí gần hơn thì đẩy bên phải.
Để lại người cuối cùng để check xem:
nếu mà khoảng cách từ cổng đó đến bên trái gần hơn thì ném vào trái,
nếu khoảng cách từ cổng đó đến bên phải gần hơn thì ném vào bên phải.
Nếu khoảng cách từ vị trí đó đến 2 bên trái phải bằng nhau thì ta phải thử đặt cả vào bên trái hoặc phái.
Lưu ý: cứ đặt hết số người vào vị trí trái hoặc phải gần cổng đó nhát.
chỉ để lại 1 người cuối cùng để backtrack, điều này sẽ tránh time limit và dễ dàng hơn.
*/
int n;
// mảng spots lưu trạng thái vị trí đã có người ngồi hay chưa và nếu có người rồi thì vị trí đó lưu người của cổng số mấy ngồi
// -1 không có người ngồi
// x là người cổng bao nhiêu ngồi.
int spots[100];
bool visited[3]; // lưu trạng thái các cổng đã duyệt hay chưa
int gates[3][2]; // mảng 2 chiều trả về số người sau cổng đó là bao nhiêu.
int answer;// lưu kết quả
bool isOpened() // hàm kiểm tra xem cổng đó đã mở để người vào hết hay chưa.
{
for (int i = 0; i < 3; i++)
{
if (!visited[i]) return false;// false ~ chưa mở
}
return true;// true ~ là mở
}
// khoảng cách từ cổng đó đến vị trí bên phải còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
int distanceToRightSpot(int start)
{
for (int i = start; i <= n; i++)
{
if (spots[i] == -1) return i - start;
}
return 100000;
}
// khoảng cách từ cổng đó đến vị trí bên trái còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
int distanceToLeftSpot(int start)
{
for (int i = start; i >= 1; i--)
{
if (spots[i] == -1) return start - i;
}
return 100000;
}
void backtrack(int sum)
{
if (isOpened()) // kiểm tra xem cổng đã mở hết chưa, nếu đã mở hết thì return giá trị.
{
if (sum < answer)answer = sum;
return;
}
for (int i = 0; i < 3; i++)
{
if (visited[i]) continue; // nếu cổng đã được mở thì ta bỏ qua.
visited[i] = true; // nếu chưa mở thì ta thăm cổng đó và đánh dấu cổng đó đã thăm.
// lưu khoảng cách tạm = số người tại cổng đó. vì khi người tại cổng X có vị trí là 3 đặt vào ô thứ 3 còn trống thì biến đếm tại ô thứ 3 là 1. ở 2 hàm
// check trái và phải thì mình chỉ check nó là 0 nên biến add cần được cộng thêm. tý cậu đọc 2 hàm check trái vs check phải là biết. nếu cậu bỏ cái add này
// đi và chạy thử kết quả nó sẽ tường minh hơn.
int add = gates[i][1];
// ta xếp hết người tại cổng đó vào vị trí. chỉ để lại 1 người cuối cùng để check.
for (int j = 0; j < gates[i][1] - 1; j++)
{
int left = distanceToLeftSpot(gates[i][0]); // khoảng cách cổng đó đến trái.
int right = distanceToRightSpot(gates[i][0]); // khoảng cách cổng đó đến phải.
// nếu trái nhỏ hơn phải thì thêm vào trái, nếu không thì thêm vào phải.
if (left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
}
//trả về khoảng cách người cuối cùng của cổng đó so với bên trái và phải.
int left = distanceToLeftSpot(gates[i][0]);
int right = distanceToRightSpot(gates[i][0]);
// nếu khoảng cách đó khách nhau thì ta check xem trái nhỏ hơn hay phải nhỏ hơn để thêm vào.
if (left != right)
{
if (left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
backtrack(sum + add);
}
// nếu khoảng cách bằng nhau thì ta cần phải đặt thử cả 2 bên trái và bên phải.
else
{
add += left;
spots[gates[i][0] + right] = i;
backtrack(sum + add);
spots[gates[i][0] + right] = -1;
spots[gates[i][0] - left] = i;
backtrack(sum + add);
spots[gates[i][0] - left] = -1;
}
// trả lại cổng chưa thăm để backtrack lại
visited[i] = false;
// trả lại những vị trí cổng đó đã ngồi.
for (int j = 1; j <= n; j++)
{
if (spots[j] == i) spots[j] = -1;
}
}
}
void readInput()
{
cin >> n;
for (int i = 0; i < 3; i++)
{
cin >> gates[i][0] >> gates[i][1];
}
}
int main()
{
freopen("input.txt", "r", stdin);
int tcs;
cin >> tcs;
// reset toàn bộ mảng để đến test case sau
for (int i = 0; i < 100; i++) spots[i] = -1;
for (int i = 0; i < 3; i++) visited[i] = false;
for (int tc = 1; tc <= tcs; tc++)
{
readInput();
answer = 10000;
backtrack(0);
cout << "#" << tc << " " << answer << endl;
}
return 0;
}
#gold mining
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int N; // kích thước map
int G; // số lượng mỏ vàng
int arr[21][21];
int arrGold[5][3]; //lưu tọa độ Vàng
int tempArrGold[5][3];
int Q[200][3];
int front, rear;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int visited[21][21];
int cntMin;
int maxCntGold;
int bfs(int i, int j){
front = rear = 0;
int cntGold = 0;
int cntStep = -1;
Q[rear][0] = i;
Q[rear][1] = j;
Q[rear++][2] = 0;
visited[i][j] = 1;
while(front < rear){
int x = Q[front][0];
int y = Q[front][1];
int cnt = Q[front++][2];
for (int dir = 0; dir < 4; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx >= 1 && nx <= N && ny >= 1 && ny <= N && visited[nx][ny] == 0 && arr[nx][ny] != 0){
Q[rear][0] = nx;
Q[rear][1] = ny;
Q[rear++][2] = cnt+1;
visited[nx][ny] = 1;
if(arr[x][y] == 2){ // nếu là mỏ vàng
cntGold++;
for (int i = 1; i <= G; i++){
if(x == arrGold[i][0] && y == arrGold[i][1]){
tempArrGold[i][2] = 1; //đánh dấu mỏ vàng đã được thăm
}
}
if(maxCntGold < cntGold){
maxCntGold = cntGold;
cntMin = 999999;
}
if(cntGold == maxCntGold && cnt+1 < cntMin){
for (int i = 1; i <= G; i++){
arrGold[i][2] = tempArrGold[i][2];
}
cntStep = cnt+1;
}
}
}
}
}
return cntStep;
}
void clear_vs(){ // xóa mảng thăm
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
visited[i][j] = 0;
}
}
}
void check_arr(){
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
if(arr[i][j] == 1){
for (int ki = 1; ki <= G; ki++){
tempArrGold[ki][2] = 0;
}
clear_vs();
int c = bfs(i, j);
if(c != -1 && c < cntMin) cntMin = c;
}
}
}
}
int main(){
int tc;
int T;
int Answer;
int R, C;
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; ++tc){
Answer = 0;
cin >> N >> G;
for (int i = 1; i <= G; i++)
{
cin >> R >> C;
tempArrGold[i][0] = arrGold[i][0] = R;
tempArrGold[i][1] = arrGold[i][1] = C;
tempArrGold[i][2] = arrGold[i][2] = 0;
}
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
cin >> arr[i][j];
}
}
for (int i = 1; i <= G; i++)
{
arr[arrGold[i][0]][arrGold[i][1]] = 2; // gán tọa độ mỏ vàng bằng 2
}
cntMin = 999999;
maxCntGold = 0;
check_arr();
if(cntMin == 999999) cntMin = -1;
cout << "Case #" << tc << endl << cntMin << endl;
if(cntMin!=-1 && maxCntGold != K)
for (int i = 0; i < K; i++)
{
if(arrGold[i][2] == 0){
cout << arrGold[i][0]+1 << " " << arrGold[i][1]+1 << endl;
}
}
}
return 0;
}
#hugo chi ong nau
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
// code 100/100
using namespace std;
int map[15][15], N, M, visit[15][15];
int dxC[6] = { 0,-1, 0, 1, 1, 1 };
int dxL[6] = { -1,-1,-1, 0, 1, 0 };
int dy[6] = { -1, 0, 1, 1, 0,-1 };
long ans;
void bt(int dem, int x, int y, long sum){
if (dem == 3){
if (ans < sum)
ans = sum;
return;
}
for (int i = 0; i < 6; i++){
if (y % 2 != 0){
int a = x + dxC[i];
int b = y + dy[i];
if (a < N && b < M && a >= 0 && b >= 0){
if (visit[a][b] == 0){
visit[a][b] = 1;
bt(dem + 1, a, b, sum + map[a][b]);
bt(dem + 1, x, y, sum + map[a][b]);
visit[a][b] = 0;
}
}
}
else{
int a = x + dxL[i];
int b = y + dy[i];
if (a < N && b < M && a >= 0 && b >= 0){
if (visit[a][b] == 0){
visit[a][b] = 1;
bt(dem + 1, a, b, sum + map[a][b]);
bt(dem + 1, x, y, sum + map[a][b]);
visit[a][b] = 0;
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++){
cin >> M >> N;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++)
cin >> map[i][j];
}
ans = 0;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
visit[i][j] = 1;
bt(0, i, j, map[i][j]);
visit[i][j] = 0;
}
}
cout << "Case #" << t << endl << ans * ans << endl;
}
return 0;
}
#hugo khu rung
#include<conio.h>
#include<iostream>
//CODE 100/100
using namespace std;
int tc, M,N,visited_chay[16][16], kimcuong[16][16], VS_hugo[16][16], KC[16][16];
int ans, cnt, damchay, ho, thoat;
int mt[16][16]; // 0:dat, 1:damchay, 2:ho, 3:loi thoat, 4:vitri ban dau hugo
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int QX[100001], QY[100001], front, rear;
int loithoat[16][16];
void init(){
for(int i=1;i<=15;i++){
for(int j=1;j<=15;j++){
mt[i][j]=visited_chay[i][j]=kimcuong[i][j]=VS_hugo[i][j]=KC[i][j]=loithoat[i][j]=0;
}
}
}
bool isSafe(int x, int y){
if(x>0 && x<=M && y>0 && y<=N) return true;
else return false;
}
void bfs_chay(){
front=rear=0;
for(int i=1;i<=M;i++){
for(int j=1;j<=N;j++){
if(mt[i][j]==1){
QX[rear]=i;
QY[rear++]=j;
visited_chay[i][j]=1;
}
}
}
while(front!=rear){
int x=QX[front];
int y=QY[front++];
for(int z=0;z<4;z++){
int nx=x+dx[z];
int ny=y+dy[z];
if(isSafe(nx,ny) && visited_chay[nx][ny]==0 && mt[nx][ny]==0){
QX[rear]=nx;
QY[rear++]=ny;
visited_chay[nx][ny]=visited_chay[x][y]+1;
}
}
}
for(int i=1;i<=15;i++){
for(int j=1;j<=15;j++){
if (visited_chay[i][j] == 0)
visited_chay[i][j] = 10000;
}
}
}
int tong;
void bt(int x, int y, int cnt){
if(loithoat[x][y]==3){
if(ans<tong) ans=tong;
}
for(int z=0;z<4;z++){
int nx=x+dx[z];
int ny=y+dy[z];
if(isSafe(nx,ny) && VS_hugo[nx][ny]==0 && ((cnt+1)<visited_chay[nx][ny])){
VS_hugo[nx][ny]=1;
tong+=kimcuong[nx][ny];
int t = mt[nx][ny]==0?1:2;
bt(nx,ny,cnt+t);
VS_hugo[nx][ny]=0;
tong-=kimcuong[nx][ny];
}
}
}
int main(){
freopen("input.txt","r",stdin);
cin>>tc;
for(int t=1;t<=tc;t++){
int x_st, y_st;
init();
cin>>M>>N>>x_st>>y_st;
cin>>damchay;
for(int i=0;i<damchay;i++){
int a, b;
cin>>a>>b;
mt[a][b]=1;
}
cin>>ho;
for(int i=0;i<ho;i++){
int a,b;
cin>>a>>b;
mt[a][b]=2;
visited_chay[a][b]=1000;
}
cin>>thoat;
for(int i=0;i<thoat;i++){
int a, b;
cin>>a>>b;
loithoat[a][b]=3;
}
for(int i=1;i<=M;i++){
for(int j=1;j<=N;j++){
cin>>kimcuong[i][j];
}
}
bfs_chay();
ans=-1;
tong=kimcuong[x_st][y_st];
VS_hugo[x_st][y_st]=1;
bt(x_st,y_st,1);
cout<<"Case #"<<t<<endl;
if(ans==-1) cout<<-1<<endl;
else cout<<ans<<endl;
}
getch();
return 0;
}
#mario climb
#include<iostream>
// code 100/100
using namespace std;
int N, M;
int arr[51][51];
int visited[51][51];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int xStart, yStart; //Tọa độ Mario
int xEnd, yEnd; // Tọa độ vàng
bool check = false;
int QX[1000001];
int QY[1000001]; // mảng lưu tọa độ
int front, rear;
void clear_visit(){
for (int i = 1; i <= N; i++){
for (int j = 1; j <= M; j++){
visited[i][j] = 0;
}
}
}
bool isSafe(int x, int y){
if(0<x && x<=N && 0<y && y<=M) return true;
else return false;
}
void bfs(int row, int col, int step){
front = rear = 0;
QX[rear] = row;
QY[rear++] = col;
visited[row][col] = 1;
while(front != rear){
int x = QX[front]; // đi từ front
int y = QY[front++];
for (int st = 1; st <= step; st++){ // có thể nhảy st bước, tối đa step bước
for (int i = 0; i < 4; i++){ // đi 4 hướng
int nx = x + dx[i]*st;
int ny = y + dy[i];
if(isSafe(nx,ny) && visited[nx][ny] == 0 && arr[nx][ny] != 0){ // là ô 1 và chưa thăm
QX[rear] = nx; // ok thì nhét vào rear
QY[rear++] = ny;
visited[nx][ny] = 1;
if(visited[xEnd][yEnd] == 1){ // tới khi tìm được vàng thì check = true rồi break
check = true;
break; // tìm thấy vàng là break
}
}
}
if(check) break; // chỉ cần có hướng đi là break
}
if(check) break; // chỉ cần có bước nhảy tối thiểu là break
}
}
int main(){
int tc;
int T;
int Answer;
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; ++tc){
cin >> N >> M;
check = false;
for (int i = 1; i <= N; i++){
for (int j = 1; j <=M; j++){
cin >> arr[i][j];
if(arr[i][j] == 2){
xStart = i;
yStart = j;
}
if(arr[i][j] == 3){
xEnd = i;
yEnd = j;
}
}
}
int step = 1;
while(!check){
clear_visit();
bfs(xStart, yStart, step); // bfs từ vị trí đầu tiên
if(check){
break;
}
step++;
}
cout << "Case #" << tc << endl << step << endl;
}
return 0;
}
#lang mac
#include<iostream>
using namespace std;
#define MAX 1001
#define INF 1000000
int t, n, a[MAX][MAX];
bool visited[MAX];
int distanced[MAX], low[MAX], parent[MAX];
bool isBright[MAX][MAX];
int timeCounter;
void initialze(){
for(int i=0; i<MAX; i++){
visited[i] = false;
parent[i] = -1;
distanced[i] = 0;
low[i] = 0;
for(int j=0; j<MAX; j++){
a[i][j] =0;
isBright[i][j] = false;
}
}
timeCounter =0;
}
int min(int a, int b){
return (a<b) ? a: b;
}
void DFS(int u){
visited[u] = true;
distanced[u] = low[u] = ++timeCounter;
for(int v=0; v<n; v++){
if(a[u][v] != 1) continue;
if(!visited[v]){
parent[v]= u;
DFS(v);
low[u] = min(low[u], low[v]);
if(low[v] > distanced[u]){
isBright[u][v] = isBright[v][u] = true;
}
}else if(v!= parent[u]){
low[u] = min(low[u], distanced[v]);
}
}
}
int findRegions(){
int regions = 0;
for(int i=0; i<n; i++){
if(!visited[i]){
DFS(i);
regions++;
}
}
return regions;
}
int findIsolatedViggales(){
int isolated =0;
for(int i=0; i<n; i++){
bool hasEdge = false;
for(int j=0; j<n; j++){
if(a[i][j] == 1){
hasEdge = true;
break;
}
}
if(!hasEdge) isolated++;
}
return isolated;
}
int countBright(){
int brightCount =0;
for(int i=0; i<n; i++){
for(int j= i+1; j<n; j++){
if(isBright[i][j]) brightCount++;
}
}
return brightCount;
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc = 1; tc<=t; tc++){
cin>>n;
initialze();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>a[i][j];
}
}
int regions = findRegions();
int isolated = findIsolatedViggales();
int bright = countBright();
cout<<regions<<" "<<isolated<<" "<<bright<<endl;
}
return 0;
}
#the frog
#include<iostream>
using namespace std;
const int MAX = 200;
#define oo 9999999
struct Leaf{
int x, y, r;
};
Leaf leaves[201];
int a[201][201], n, t;
int visited[201], val[201];
void input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>leaves[i].x >> leaves[i].y >> leaves[i].r;
}
for(int i=0; i<n; i++){
val[i] = oo,visited[i] = 0;
}
}
void process_input(){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int temp;
temp = (leaves[i].x - leaves[j].x) * (leaves[i].x - leaves[j].x) + (leaves[i].y - leaves[j].y) * (leaves[i].y - leaves[j].y);
if(temp!=0){
temp = temp;
}
if(i!=j){
if(temp<= (40 + leaves[i].r+ leaves[j].r) * (40 + leaves[i].r+ leaves[j].r)) a[i][j] =1;
else if(temp > (90 + leaves[i].r+ leaves[j].r) * (90 + leaves[i].r+ leaves[j].r)) a[i][j] = oo;
else if(temp > (40 + leaves[i].r+ leaves[j].r) * (40 + leaves[i].r+ leaves[j].r)
&&(90 + leaves[i].r+ leaves[j].r) * (90 + leaves[i].r+ leaves[j].r) >=temp) a[i][j] =1000;
}else a[i][j] = oo;
}
}
}
int solve(){
val[0] =0;
visited[0] = 1;
for(int i=0; i<n; i++){
val[i] = a[0][i];
}
while(true){
int temp = oo, inx = -1;
for(int i=0; i<n; i++){
if(visited[i] == 0 && val[i] < temp){
temp = val[i];
inx = i;
}
}
if(inx == n-1 || inx == -1) break;
visited[inx] =1;
for(int i = 0; i<n; i++){
if(visited[i] ==0 && a[inx][i] <oo){
if(val[i] > val[inx] + a[inx][i]){
val[i] = val[inx] + a[inx][i];
}
}
}
}
if(val[n-1] == oo){
cout<<-1<<endl;
}else{
cout<<val[n-1]/1000<<" "<<val[n-1]%1000<<endl;
}
return 0;
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
input();
process_input();
solve();
}
return 0;
}
#nuoc bien
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
// code 100/100
int N, M;
int arr[101][101];
int visited[101][101];
int Q[10002][2];
int Qsea[10002][2];
int frontb, rearb;
int cntArea;
int front, rear;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int mucnuoc;
int cntVisit;
using namespace std;
void bfs_cnt_area(){
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
front = rear = 0;
if(visited[i][j] == 0){
cntVisit++;
Q[rear][0] = i;
Q[rear++][1] = j;
visited[i][j] = 1;
while(front != rear){
int row = Q[front][0];
int col = Q[front++][1];
for (int i = 0; i < 4; i++){
int x = row+dx[i];
int y = col + dy[i];
if(x >= 0 && x < N && y >= 0 && y < M && visited[x][y] == 0){
cntVisit++;
visited[x][y] = 1;
Q[rear][0] = x;
Q[rear++][1] = y;
}
}
}
if(rear != 0 && cntVisit < N*M)
return;
}
}
}
return;
}
void loang_bien(){
while(rearb != frontb){
int row = Qsea[frontb][0];
int col = Qsea[frontb++][1];
for (int i = 0; i < 4; i++){
int x = row+dx[i];
int y = col+dy[i];
if(x >= 0 && x < N && y >= 0 && y < M && arr[x][y] <= mucnuoc && visited[x][y] == 0){
visited[x][y] = 1;
Qsea[rearb][0] = x;
Qsea[rearb++][1] = y;
cntVisit++;
}
}
}
}
void clear(){
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
visited[i][j] = 0;
}
}
}
int main(){
int test_case = 0;
int T;
int Answer;
freopen("input.txt", "r", stdin);
while(true){
cin >> N >> M;
if(N != 0 && M != 0){
test_case++;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
cin >> arr[i][j];
visited[i][j] = 0;
}
}
mucnuoc = 0;
while(mucnuoc < 1001){
frontb = rearb = 0;
clear();
cntVisit = 0;
for (int i = 0; i < N; i++){
if(arr[i][0] <= mucnuoc ){
visited[i][0] = 1;
Qsea[rearb][0] = i;
Qsea[rearb++][1] = 0;
cntVisit++;
//break;
}
if(arr[i][M-1] <= mucnuoc){
visited[i][M-1] = 1;
Qsea[rearb][0] = i;
Qsea[rearb++][1] = M-1;
cntVisit++;
}
}
for (int i = 1; i < M-1; i++){
if(arr[0][i] <= mucnuoc ){
visited[0][i] = 1;
Qsea[rearb][0] = 0;
Qsea[rearb++][1] = i;
cntVisit++;
//break;
}
if(arr[N-1][i] <= mucnuoc){
visited[N-1][i] = 1;
Qsea[rearb][0] = N-1;
Qsea[rearb++][1] = i;
cntVisit++;
}
}
if(rearb != 0){
loang_bien();
bfs_cnt_area();
if(cntVisit < N*M){
break;
}
}
mucnuoc++;
}
if(cntVisit == N*M)
cout << "Case " << test_case << ": " << "Island never splits." << endl;
else cout << "Case " << test_case << ": " << "Island splits when ocean rises " << mucnuoc << " feet." << endl;
}
if(N==0 && M == 0) break;
}
return 0;
}
#nuoc bien
#include<iostream>
using namespace std;
const int MAX = 101;
int t, n, m, a[1001][1001];
int visited[1001][1001];
int qX[1000001], qY[1000001];
int frontX, frontY, rearX, rearY;
int Hmax;
int dx[4] = {1, 0, -1 ,0};
int dy[4] = {0, -1, 0, 1};
int check_connect[1001][1001];
void initQueue(){
frontX = frontY = rearX = rearY = -1;
}
int isEmpty(){
return frontX == rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
if(!isEmpty()){
frontX++;
return qX[frontX];
}
return -1;
}
int deQueueY(){
if(!isEmpty()){
frontY++;
return qX[frontY];
}
return -1;
}
void reset(){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
visited[i][j] = 0;
check_connect[i][j] = 0;
}
}
}
void AddSea(int x){
for (int i = 0; i < m; i++){
a[0][i] = x;
a[n - 1][i] = x;
}
for (int i = 0; i < n; i++){
a[i][0] = x;
a[i][m - 1] = x;
}
}
void BFS_ocean(int x, int y, int ocean){
initQueue();
enQueue(x, y);
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++) visited[i][j] = -1;
}
visited[x][y] = ocean;
while (!isEmpty()){
int curX = deQueueX();
int curY = deQueueY();
for (int i = 0; i < 4; i++){
int tempX = curX + dx[i];
int tempY = curY + dy[i];
if (tempX >= 0 && tempX < n && tempY >= 0 && tempY < m && visited[tempX][tempY] == -1 && a[tempX][tempY] <= visited[curX][curY]){
visited[tempX][tempY] = visited[curX][curY];
enQueue(tempX, tempY);
}
}
}
}
int BFS_island(){
int x, y;
int before = 0, after = 0;
bool flag = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (visited[i][j] == -1){
if (!flag){
x = i;
y = j;
flag = 1;
}
before++;
}
}
}
if (before == 0) return -1;
initQueue();
enQueue(x,y);
visited[x][y] = -2;
while (!isEmpty()){
int curX = deQueueX();
int curY = deQueueY();
after ++;
for (int i = 0; i < 4; i++){
int tempX = curX + dx[i];
int tempY = curY + dy[i];
if (tempX >= 0 && tempX < n && tempY >= 0 && tempY < m && visited[tempX][tempY] == -1){
visited[tempX][tempY] = -2;
enQueue(tempX, tempY);
}
}
}
if (before == after) return -2;
if (before > after) return visited[0][0];
}
int main(){
freopen("input.txt", "r", stdin);
while (cin >> n >> m){
t++;
if (n + m == 0) break;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cin >> a[i][j];
n += 2;
m += 2;
for (int z = 0; ; z++){
AddSea(z);
int x =0, y=0;
BFS_ocean(x, y, z);
int res = BFS_island();
if (res == -1){
cout << "Case " << t <<": ";
cout << "Island never splits." << endl;
break;
}
if (res == -2) continue;
else {
cout << "Case " << t <<": ";
cout << "Island splits when ocean rises " << res << " feet." << endl;
break;
}
}
}
return 0;
}
#painting
#include<iostream>
using namespace std;
int t, n;
int a[31][31];
int aMau[31];
int maxCount;
bool toMau(int index){
for(int i=0; i<index; i++){
if(a[index][i] ==1 && aMau[i] == aMau[index]){
return false;
}
}
return true;
}
void backtrack(int index){
if(index == n){
maxCount ++;
return;
}
for(int i=1; i<=4; i++){
if(!aMau[index]){
aMau[index] = i;
if(toMau(index)){
backtrack(index +1);
}
aMau[index] =0;
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>a[i][j];
}
aMau[i] =0;
}
maxCount =0;
backtrack(0);
cout<<"Case #"<<tc<<endl;
cout<<maxCount<<endl;
}
return 0;
}
#vinhdaovang
#include<iostream>
using namespace std;
const int MAX = 25;
const int INF = 1e9;
int n,g;
int grid[MAX][MAX];
int goldX[MAX], goldY[MAX];
//int gold[MAX][MAX];
int qX[10000000], qY[10000000];
int frontX, frontY, rearX, rearY;
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dist[MAX][MAX];
void initQueue(){
frontX = frontY = rearX = rearY = -1;
}
int isEmpty(){
return frontX== rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
int bfs(int startX, int startY){
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
dist[i][j] = INF;
}
}
initQueue();
enQueue(startX, startY);
dist[startX][startY] = 0;
while(!isEmpty()){
int pX = deQueueX();
int pY = deQueueY();
for(int i=0; i<4; ++i){
int newX = pX + directions[i][0];
int newY = pY + directions[i][1];
if(newX>=0 && newX<n && newY>=0 && newY<n && grid[newX][newY] ==1 && dist[newX][newY] == INF){
dist[newX][newY] = dist[pX][pY] +1;
enQueue(newX, newY);
}
}
}
int maxDist = 0;
for(int i=0; i<g; ++i){
int goldDist = dist[goldX[i]][goldY[i]];
if(goldDist == INF) return INF;
maxDist = max(maxDist, goldDist);
}
return maxDist;
}
int main(){
freopen("input.txt", "r", stdin);
int t;
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n>>g;
for(int i=0; i<g; ++i){
cin>>goldX[i]>>goldY[i];
goldX[i]--;
goldY[i]--;
}
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
cin>>grid[i][j];
}
}
int minMaxDist = INF;
int maxGold =0;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(grid[i][j] == 1){
bool isGold = false;
for(int k=0; k<g; ++k){
if(i == goldX[k] && j == goldY[k]){
isGold = true;
break;
}
}
if(!isGold)
{
int maxDist = bfs(i,j);
minMaxDist = min(minMaxDist, maxDist);
}
}
}
}
if(minMaxDist == INF){
cout<<"Case #"<<tc<<endl;
cout<<-1<<endl;
}else{
cout<<"Case #"<<tc<<endl;
cout<<minMaxDist<<endl;
}
}
return 0;
}
#turnovergame
#include<iostream>
using namespace std;
char a[5][5];
int t;
int minCount;
int directions[4][2] = {{1,0}, {-1,0}, {0, 1}, {0, -1}};
void changeColor(int x, int y){
if(a[x][y] == 'b'){
a[x][y] = 'w';
}else{
a[x][y] = 'b';
}
for(int i=0; i<4; i++){
int tempX = x + directions[i][0];
int tempY = y + directions[i][1];
if(tempX>=0 && tempX <4 && tempY>=0 && tempY <4){
if(a[tempX][tempY] == 'b'){
a[tempX][tempY] = 'w';
}else{
a[tempX][tempY] = 'b';
}
}
}
}
bool check(){
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
if(a[i][j] != a[0][0]){
return false;
}
}
}
return true;
}
void backtrack(int index, int dem){
if(check()){
minCount = min(minCount, dem);
return;
}
if(index == 16){
return;
}
int row = index/4;
int col = index%4;
changeColor(row, col);
backtrack(index+1, dem +1); // doi mau
changeColor(row, col);
backtrack(index+1, dem); // tra lai mau
}
int main(){
//freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
minCount = 1000000;
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
cin>>a[i][j];
}
}
backtrack(0,0);
if(minCount != 1000000){
cout<<"Case #"<<tc<<endl;
cout<<minCount<<endl;
}else{
cout<<"Case #"<<tc<<endl;
cout<<"impossible"<<endl;
}
}
return 0;
}
#nangcapmaytinh
#include<iostream>
using namespace std;
int tc,n,slggoi,gia[20],goi[30][23], can[20],slgcan;
int visited[21],minn;
bool checkgoi(int m, int i){
for(int j=0;j<goi[i][1];j++){
if(goi[i][j+2]==m) return true;
}
return false;
}
void backtrack(int st,int sum){
if(st==slgcan){
if(sum<minn){
minn=sum;
return;
}
}
if(sum>=minn) return;
if(visited[can[st]]>=1){
backtrack(st+1,sum);
}
else{
visited[can[st]]++;
backtrack(st+1,sum+gia[can[st]-1]);
visited[can[st]]--;
for(int i=0;i<slggoi;i++){
if(checkgoi(can[st],i) ){
for(int j=0;j<goi[i][1];j++){
visited[goi[i][2+j]]++;
}
backtrack(st+1,sum+goi[i][0]);
for(int j=0;j<goi[i][1];j++){
visited[goi[i][2+j]]--;
}
}
}
}
}
int main(){
freopen("input.txt","r",stdin);
cin>>tc;
for(int t=1;t<=tc;t++){
cin>>n;
for(int i=0;i<n;i++){
cin>>gia[i];
}
cin>>slggoi;
for(int i=0;i<slggoi;i++){
cin>>goi[i][0]>>goi[i][1];
for(int j=0;j<goi[i][1];j++){
cin>>goi[i][2+j];
}
}
cin>>slgcan;
for(int i=0;i<slgcan;i++){
cin>>can[i];
}
minn=100000;
backtrack(0,0);
cout<<"#"<<t<<" "<<minn<<endl;
}
return 0;
}
#include <iostream>
using namespace std;
const int dir[4][4] = {
{1, 2, 5, 6},
{1, 3, 6, 7},
{1, 2, 4, 7},
{1, 3, 4, 5},
};
const int type[8][4] = {
{},
{1, 1, 1, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1}
};
const int dX[] = {-1, 0, 1, 0};
const int dY[] = {0, 1, 0, -1};
int frontX, frontY, rearX, rearY, t, n, m, map[60][60], p, visited[60][60], res;
int qX[1000001], qY[1000001];
bool map_dir[10][10];
void initQueue(){
frontX = rearX = frontY = rearY = -1;
}
bool IsEmpty(){
return frontX == rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
void BFS(int x, int y, int p){
initQueue();
enQueue(x, y);
visited[x][y] = 1;
while (!IsEmpty()){
int curX = deQueueX();
int curY = deQueueY();
if (visited[curX][curY] > p){
continue;
}
for (int index = 0; index < 4; index++){
int pipedir = type[map[curX][curY]][index];
if (pipedir == 0) continue;
int tx = curX + dX[index];
int ty = curY + dY[index];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] != 0 && visited[tx][ty] == -1) {
if (map_dir[index][map[tx][ty]] == 1){
visited[tx][ty] = visited[curX][curY] + 1;
enQueue(tx, ty);
}
}
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin >> t;
for (int tc = 1; tc <= t; tc++){
int hugoX, hugoY;
cin >> n >> m >> hugoX >> hugoY >> p;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> map[i][j];
visited[i][j] = -1;
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++) map_dir[i][j] = 0;
}
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) map_dir[i][dir[i][j]] = 1;
BFS(hugoX,hugoY, p);
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++){
if (visited[i][j] <= p && visited[i][j] > 0) cnt ++;
}
}
cout << "Case #" << tc << endl;
cout << cnt << endl;
}
return 0;
}
#hugo
#include <iostream>
using namespace std;
int t, n, m ,fires, diamond[20][20], lakes, visited_fire[20][20], frontX, frontY, rearX, rearY, doors, maxx, visited_hugo[20][20], max_time;
bool map_doors[20][20], map_lake[20][20];
int list_firesX[1000], list_firesY[1000], list_lakesX[1000], list_lakesY[1000], qX[50000], qY[50000];
const int dX[] = {1, -1, 0, 0};
const int dY[] = {0, 0, 1, -1};
void InitQueue(){
frontX = rearX = frontY = rearY = -1;
}
bool IsEmpty(){
return frontX == rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
void BFS_fire(){
InitQueue();
for (int i = 0; i < fires; i++){
enQueue(list_firesX[i], list_firesY[i]);
visited_fire[list_firesX[i]][list_firesY[i]] = 0;
}
for (int i = 0; i < lakes; i++){
visited_fire[list_lakesX[i]][list_lakesY[i]] = -1;
}
while (!IsEmpty()){
int curX = deQueueX();
int curY = deQueueY();
for (int i = 0; i < 4; i++){
int tx = curX + dX[i];
int ty = curY + dY[i];
if (tx >= 0 && tx < n && ty >= 0 && ty< m && visited_fire[tx][ty] != -1){
if (visited_fire[tx][ty] == 0){
visited_fire[tx][ty] = visited_fire[curX][curY] + 1;
enQueue(tx, ty);
}
}
}
}
}
void Backtrack (int x, int y, int time, int cnt_diamond){
if (map_doors[x][y] == 1){
if (maxx < cnt_diamond) maxx = cnt_diamond;
}
for (int i = 0; i < 4; i++){
int u = x + dX[i];
int v = y + dY[i];
if (u >= 0 && u < n && v >= 0 && v < m){
if (visited_hugo[u][v] == -1){
visited_hugo[u][v] = 1;
Backtrack(u, v, time + 2, cnt_diamond + diamond[u][v]);
visited_hugo[u][v] = -1;
}
else {
if (visited_hugo[u][v] == 0 && ((visited_fire[u][v] > time + 1) || (visited_fire[u][v] == 0))){
visited_hugo[u][v] = 1;
Backtrack(u, v, time + 1, cnt_diamond + diamond[u][v]);
visited_hugo[u][v] = 0;
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin >> t;
for (int tc = 1; tc <= t; tc++){
int hugoX, hugoY;
cin >> n >> m >> hugoX >> hugoY;
hugoX --;
hugoY --;
cin >> fires; // fires
for (int i = 0; i < fires; i++){
int a, b;
cin >> a >> b;
list_firesX[i] = --a;
list_firesY[i] = --b;
}
for (int i = 0; i < 20; i++){
for (int j = 0; j < 20; j++){
map_doors[i][j] = 0;
visited_fire[i][j] = 0;
visited_hugo[i][j] = 0;
map_lake[i][j] = 0;
}
}
cin >> lakes;
for (int i = 0; i < lakes; i++){
int a, b;
cin >> a >> b;
list_lakesX[i] = --a;
list_lakesY[i] = --b;
visited_hugo[a][b] = -1;
map_lake[a][b] = 1;
}
cin >> doors;
for (int i = 0; i < doors; i++){
int a, b;
cin >> a >> b;
a--; b--;
map_doors[a][b] = 1;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++) {
cin >> diamond[i][j];
}
}
maxx = -1;
BFS_fire();
visited_hugo[hugoX][hugoY] = 1;
Backtrack(hugoX, hugoY, 0, diamond[hugoX][hugoY]);
cout << "Case #" << tc << endl;
cout << maxx << endl;
}
return 0;
}
#dominos
#include <iostream>
using namespace std;
// code 100/100
int map[7][8];
int domino[7][7];
int visit[7][8];
int ans;
int dx[2] = {1,0};
int dy[2] = {0,1};
void backtrack(int index){
if (index == 56){
ans++;
return;
}
int x = index/ 8;
int y = index % 8;
if (!visit[x][y]){
for (int d = 0; d < 2; d++){
int tx = x + dx[d];
int ty = y + dy[d];
if (tx>=0 && tx <7 && ty>=0 && ty<8 && !visit[tx][ty] && !domino[map[x][y]][map[tx][ty]]){
visit[x][y] = visit[tx][ty] = 1;
domino[map[x][y]][map[tx][ty]] = domino[map[tx][ty]][map[x][y]] = 1;
backtrack (index+1);
visit[x][y] = visit[tx][ty] = 0;
domino[map[x][y]][map[tx][ty]] = domino[map[tx][ty]][map[x][y]] = 0;
}
}
}
else backtrack(index+1);
}
int main(){
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for (int tC = 1; tC <= T; tC++){
for (int i = 0; i < 7; i++)
for (int j = 0; j < 8; j++){
cin >> map[i][j];
visit[i][j] = 0;
}
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
domino[i][j] = 0;
ans = 0;
backtrack(0);
cout << "#" << tC << " " << ans << endl;
}
return 0;
}
#hugoditau
#include<iostream>
using namespace std;
int t, n;
int hoanvi[6][3] =
{ {1, 2, 3},
{1, 3, 2},
{2, 1, 3},
{2, 3, 1},
{3, 1, 2},
{3, 2, 1}};
int listIndex[4];
int listSL[4];
int a[70], trace[70];
const int INF = 1e9;
int min1;
void reset(int cuaso){
for(int i=0; i<=n; i++){
if(trace[i] == cuaso){
a[0] -= a[i];
trace[i] = 0;
a[i] = 0;
}
}
}
int datViTri(int cua, int vitri, int sl){
int index_up = vitri;
int index_down = vitri;
for (int i = 0; i < sl; i++)
{
if(i == sl - 1){
if(index_up <= n && index_down > 0)
if(trace[index_up] != 0 && trace[index_down] != 0){
index_up++;
index_down--;
if(index_up <= n && index_down > 0)
if(trace[index_up] == 0 && trace[index_down] == 0){
return index_up - vitri + 1;
}
}
}
while (true)
{
if(index_up <= n)
if(trace[index_up] == 0){
a[index_up] = index_up - vitri + 1;
trace[index_up] = cua;
a[0] += a[index_up];
break;
}
if(index_down >= 1)
if(trace[index_down] == 0){
a[index_down] = vitri - index_down + 1;
trace[index_down] = cua;
a[0] += a[index_down];
break;
}
index_up++;
index_down--;
}
}
return 0;
}
void backtrack(int _case, int thutu, int point){
int cuaso = hoanvi[_case][thutu];
int vitriCua = listIndex[cuaso];
int sl = listSL[cuaso];
if(thutu == 3){
if(min1 > a[0]){
min1 = a[0];
}
return;
}
int ret = datViTri(cuaso, vitriCua, sl);
if(ret == 0){
backtrack(_case, thutu +1 ,a[0]);
}else if(ret > 0){
//chon trai
int index = vitriCua - ret +1;
a[index] = ret;
trace[index] = cuaso;
a[0] += ret;
backtrack(_case, thutu + 1, a[0]);
a[index] = 0;
trace[index] = 0;
a[0] -= ret;
//chon phai
index = vitriCua + ret -1;
a[index] = ret;
trace[index] = cuaso;
a[0] += ret;
backtrack(_case, thutu +1, a[0]);
a[index] = 0;
trace[index] = 0;
a[0] -= ret;
}
reset(cuaso);
}
int main(){
//freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
cin >> n;
for (int i = 1; i <= 3; i++)
{
cin >> listIndex[i];
cin >> listSL[i];
}
for (int i = 0; i <= n; i++)
{
a[i] = 0;
trace[i] = 0;
}
min1 = INF;
for (int i = 0; i < 6; i++)
{
backtrack(i,0,0);
}
cout<<"Case #"<<tc<<endl;
cout<<min1<<endl;
}
return 0;
}
#fishing
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
// có 3 cổng. sắp xếp số người của mỗi cổng sao cho khoảng cách số người của cổng đó cách cổng đó ít nhất.
/* hướng giải bài toán :
nếu bên trái còn vị trí gần hơn thì đẩy hết vào trái, bên phải còn vị trí gần hơn thì đẩy bên phải.
Để lại người cuối cùng để check xem:
nếu mà khoảng cách từ cổng đó đến bên trái gần hơn thì ném vào trái,
nếu khoảng cách từ cổng đó đến bên phải gần hơn thì ném vào bên phải.
Nếu khoảng cách từ vị trí đó đến 2 bên trái phải bằng nhau thì ta phải thử đặt cả vào bên trái hoặc phái.
Lưu ý: cứ đặt hết số người vào vị trí trái hoặc phải gần cổng đó nhát.
chỉ để lại 1 người cuối cùng để backtrack, điều này sẽ tránh time limit và dễ dàng hơn.
*/
int n;
// mảng spots lưu trạng thái vị trí đã có người ngồi hay chưa và nếu có người rồi thì vị trí đó lưu người của cổng số mấy ngồi
// -1 không có người ngồi
// x là người cổng bao nhiêu ngồi.
int spots[100];
bool visited[3]; // lưu trạng thái các cổng đã duyệt hay chưa
int gates[3][2]; // mảng 2 chiều trả về số người sau cổng đó là bao nhiêu.
int answer;// lưu kết quả
bool isOpened() // hàm kiểm tra xem cổng đó đã mở để người vào hết hay chưa.
{
for (int i = 0; i < 3; i++)
{
if (!visited[i]) return false;// false ~ chưa mở
}
return true;// true ~ là mở
}
// khoảng cách từ cổng đó đến vị trí bên phải còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
int distanceToRightSpot(int start)
{
for (int i = start; i <= n; i++)
{
if (spots[i] == -1) return i - start;
}
return 100000;
}
// khoảng cách từ cổng đó đến vị trí bên trái còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
int distanceToLeftSpot(int start)
{
for (int i = start; i >= 1; i--)
{
if (spots[i] == -1) return start - i;
}
return 100000;
}
void backtrack(int sum)
{
if (isOpened()) // kiểm tra xem cổng đã mở hết chưa, nếu đã mở hết thì return giá trị.
{
if (sum < answer)answer = sum;
return;
}
for (int i = 0; i < 3; i++)
{
if (visited[i]) continue; // nếu cổng đã được mở thì ta bỏ qua.
visited[i] = true; // nếu chưa mở thì ta thăm cổng đó và đánh dấu cổng đó đã thăm.
// lưu khoảng cách tạm = số người tại cổng đó. vì khi người tại cổng X có vị trí là 3 đặt vào ô thứ 3 còn trống thì biến đếm tại ô thứ 3 là 1. ở 2 hàm
// check trái và phải thì mình chỉ check nó là 0 nên biến add cần được cộng thêm. tý cậu đọc 2 hàm check trái vs check phải là biết. nếu cậu bỏ cái add này
// đi và chạy thử kết quả nó sẽ tường minh hơn.
int add = gates[i][1];
// ta xếp hết người tại cổng đó vào vị trí. chỉ để lại 1 người cuối cùng để check.
for (int j = 0; j < gates[i][1] - 1; j++)
{
int left = distanceToLeftSpot(gates[i][0]); // khoảng cách cổng đó đến trái.
int right = distanceToRightSpot(gates[i][0]); // khoảng cách cổng đó đến phải.
// nếu trái nhỏ hơn phải thì thêm vào trái, nếu không thì thêm vào phải.
if (left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
}
//trả về khoảng cách người cuối cùng của cổng đó so với bên trái và phải.
int left = distanceToLeftSpot(gates[i][0]);
int right = distanceToRightSpot(gates[i][0]);
// nếu khoảng cách đó khách nhau thì ta check xem trái nhỏ hơn hay phải nhỏ hơn để thêm vào.
if (left != right)
{
if (left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
backtrack(sum + add);
}
// nếu khoảng cách bằng nhau thì ta cần phải đặt thử cả 2 bên trái và bên phải.
else
{
add += left;
spots[gates[i][0] + right] = i;
backtrack(sum + add);
spots[gates[i][0] + right] = -1;
spots[gates[i][0] - left] = i;
backtrack(sum + add);
spots[gates[i][0] - left] = -1;
}
// trả lại cổng chưa thăm để backtrack lại
visited[i] = false;
// trả lại những vị trí cổng đó đã ngồi.
for (int j = 1; j <= n; j++)
{
if (spots[j] == i) spots[j] = -1;
}
}
}
void readInput()
{
cin >> n;
for (int i = 0; i < 3; i++)
{
cin >> gates[i][0] >> gates[i][1];
}
}
int main()
{
freopen("input.txt", "r", stdin);
int tcs;
cin >> tcs;
// reset toàn bộ mảng để đến test case sau
for (int i = 0; i < 100; i++) spots[i] = -1;
for (int i = 0; i < 3; i++) visited[i] = false;
for (int tc = 1; tc <= tcs; tc++)
{
readInput();
answer = 10000;
backtrack(0);
cout << "#" << tc << " " << answer << endl;
}
return 0;
}
#hugo chiongnau
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
// code 100/100
using namespace std;
int map[15][15], N, M, visit[15][15];
int dxC[6] = { 0,-1, 0, 1, 1, 1 };
int dxL[6] = { -1,-1,-1, 0, 1, 0 };
int dy[6] = { -1, 0, 1, 1, 0,-1 };
long ans;
void bt(int dem, int x, int y, long sum){
if (dem == 3){
if (ans < sum)
ans = sum;
return;
}
for (int i = 0; i < 6; i++){
if (y % 2 != 0){
int a = x + dxC[i];
int b = y + dy[i];
if (a < N && b < M && a >= 0 && b >= 0){
if (visit[a][b] == 0){
visit[a][b] = 1;
bt(dem + 1, a, b, sum + map[a][b]);
bt(dem + 1, x, y, sum + map[a][b]);
visit[a][b] = 0;
}
}
}
else{
int a = x + dxL[i];
int b = y + dy[i];
if (a < N && b < M && a >= 0 && b >= 0){
if (visit[a][b] == 0){
visit[a][b] = 1;
bt(dem + 1, a, b, sum + map[a][b]);
bt(dem + 1, x, y, sum + map[a][b]);
visit[a][b] = 0;
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++){
cin >> M >> N;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++)
cin >> map[i][j];
}
ans = 0;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
visit[i][j] = 1;
bt(0, i, j, map[i][j]);
visit[i][j] = 0;
}
}
cout << "Case #" << t << endl << ans * ans << endl;
}
return 0;
}
#mario climb
#include<iostream>
// code 100/100
using namespace std;
int N, M;
int arr[51][51];
int visited[51][51];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int xStart, yStart; //Tọa độ Mario
int xEnd, yEnd; // Tọa độ vàng
bool check = false;
int QX[1000001];
int QY[1000001]; // mảng lưu tọa độ
int front, rear;
void clear_visit(){
for (int i = 1; i <= N; i++){
for (int j = 1; j <= M; j++){
visited[i][j] = 0;
}
}
}
bool isSafe(int x, int y){
if(0<x && x<=N && 0<y && y<=M) return true;
else return false;
}
void bfs(int row, int col, int step){
front = rear = 0;
QX[rear] = row;
QY[rear++] = col;
visited[row][col] = 1;
while(front != rear){
int x = QX[front]; // đi từ front
int y = QY[front++];
for (int st = 1; st <= step; st++){ // có thể nhảy st bước, tối đa step bước
for (int i = 0; i < 4; i++){ // đi 4 hướng
int nx = x + dx[i]*st;
int ny = y + dy[i];
if(isSafe(nx,ny) && visited[nx][ny] == 0 && arr[nx][ny] != 0){ // là ô 1 và chưa thăm
QX[rear] = nx; // ok thì nhét vào rear
QY[rear++] = ny;
visited[nx][ny] = 1;
if(visited[xEnd][yEnd] == 1){ // tới khi tìm được vàng thì check = true rồi break
check = true;
break; // tìm thấy vàng là break
}
}
}
if(check) break; // chỉ cần có hướng đi là break
}
if(check) break; // chỉ cần có bước nhảy tối thiểu là break
}
}
int main(){
int tc;
int T;
int Answer;
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; ++tc){
cin >> N >> M;
check = false;
for (int i = 1; i <= N; i++){
for (int j = 1; j <=M; j++){
cin >> arr[i][j];
if(arr[i][j] == 2){
xStart = i;
yStart = j;
}
if(arr[i][j] == 3){
xEnd = i;
yEnd = j;
}
}
}
int step = 1;
while(!check){
clear_visit();
bfs(xStart, yStart, step); // bfs từ vị trí đầu tiên
if(check){
break;
}
step++;
}
cout << "Case #" << tc << endl << step << endl;
}
return 0;
}
#mario climb vinh
#include<iostream>
using namespace std;
int n, m;
int a[51][51];
int visited[51][51];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int startX, startY, endX, endY;
bool check;
int qX[100001], qY[100001];
int frontX, frontY, rearX, rearY;
void initQueue(){
frontX = frontY = rearX = rearY = -1;
}
bool isEmpty(){
return frontX == rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
void reset(){
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
visited[i][j] = 0;
}
}
}
void BFS(int x, int y, int step){
initQueue();
enQueue(x, y);
visited[x][y] = 1;
while(!isEmpty()){
int curX = deQueueX();
int curY = deQueueY();
for(int st =1; st<=step; st++){
for(int i=0; i<4; i++){
int tx = curX + dx[i] * st;
int ty = curY + dy[i];
if(tx>0 && tx<=n && ty>0 && ty<=m && visited[tx][ty] == 0 && a[tx][ty] !=0){
enQueue(tx, ty);
visited[tx][ty] =1;
if(visited[endX][endY] == 1){
check = true;
break;
}
}
}
if(check) break;
}
if(check) break;
}
}
int main(){
int t, tc;
cin>>t;
for(tc=1; tc<=t; tc++){
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>a[i][j];
if(a[i][j] == 2){
startX = i; startY = j;
}
if(a[i][j] == 3){
endX =i; endY =j;
}
}
}
int step =1;
check = false;
while(!check){
reset();
BFS(startX, startY, step);
if(check) break;
step++;
}
cout<<"#"<<tc<<" "<<step<<endl;
}
return 0;
}
#hugo chiongnau vinh
#include<iostream>
using namespace std;
int t, tc, n, m;
int a[35][35];
int visited[35][35];
int res;
int dx[] = { 1,-1,-1,0,2,-2};
int dy[] = { -1,-1,1,1,0,0};
void reset(){
for(int i =1; i<=35; i++){
for(int j=1; j<=35; j++){
visited[i][j] =0;
}
}
}
void backtrack(int x, int y, int cnt, int sum){
if(cnt == 4){
res = max(res, sum);
return;
}
for(int i=0; i<6; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx>0 && tx<=m && ty>0 && ty<=n && visited[tx][ty] ==0 && a[tx][ty] !=0){
visited[tx][ty] =1;
backtrack(tx, ty, cnt+1, sum + a[tx][ty]);
backtrack(x, y, cnt +1, sum + a[tx][ty]);
visited[tx][ty] = 0;
}
}
}
int main(){
cin>>t;
for(tc =1; tc<=t; tc++){
cin>>n>>m;
m =m*2;
for(int i=1;i<=m; i = i+2){
for(int j =1;j <=n; j++){
if(j%2 ==1){
cin>>a[i][j];
visited[i][j] =0;
}
else{
cin>>a[i+1][j];
visited[i+1][j] = 0;
}
}
}
reset();
res =0;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(a[i][j] !=0){
visited[i][j] =1;
backtrack(i, j, 1, a[i][j]);
visited[i][j] =0;
}
}
}
cout<<"#"<<tc<< " "<<res*res<<endl;
}
return 0;
}
#laughing bomb
#include<iostream>
using namespace std;
int qX[11000], qY[11000], a[1001][1001], visited[1001][1001];
int frontX, frontY, rearX, rearY;
int t, m, n;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int xBom, yBom;
int max1 =1;
void initQueue(){
frontX = frontY = rearX = rearY = -1;
}
int isEmptyX(){
if(frontX == rearX) return 1;
return 0;
}
int isEmptyY(){
if(frontY == rearY) return 1;
return 0;
}
void enQueueX(int x){
rearX ++;
qX[rearX] = x;
}
void enQueueY(int y){
rearY++;
qY[rearY] = y;
}
int deQueueX(){
if(!isEmptyX()){
frontX++;
return qX[frontX];
}
return -1;
}
int deQueueY(){
if(!isEmptyY()){
frontY++;
return qY[frontY];
}
return -1;
}
void BFS(int x, int y){
initQueue();
enQueueX(x);
enQueueY(y);
visited[x][y] =1;
max1 = -1;
while(!isEmptyX()){
int currentX, currentY;
currentX = deQueueX();
currentY = deQueueY();
for(int k=0; k<4;k++){
int tempX, tempY;
tempX = currentX + dx[k];
tempY = currentY + dy[k];
if(tempX >= 0 && tempX<n && tempY>=0 && tempY<m && a[tempX][tempY] == 1 && visited[tempX][tempY] ==0){
visited[tempX][tempY] = visited[currentX][currentY] +1;
if(visited[tempX][tempY] > max1){
max1 = visited[tempX][tempY];
}
enQueueX(tempX);
enQueueY(tempY);
}
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=0; tc<t;tc++){
cin>>m>>n;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>a[i][j];
visited[j][i] = 0;
}
}
cin>>yBom>>xBom;
yBom --;
xBom --;
BFS(xBom, yBom);
cout<<max1<<endl;
}
return 0;
}
#checking cube
#include<iostream>
using namespace std;
int t, n;
int a[61];
int cnt;
void cube(){
for(int i=0; i<61; i++){
a[i] = i*i*i;
}
}
void backtrack(int cubeNum, int index, int sum){
if(cubeNum >=5){
if(sum== n){
cnt++;
}
return;
}
for(int i = index; i<61; i++){
backtrack(cubeNum +1, i, sum + a[i]);
if(sum >n){
break;
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
cube();
for(int tc=1; tc<=t; tc++){
cin>>n;
cnt=0;
backtrack(0, 0, 0);
cout<<"#"<<tc<<" "<<cnt<<endl;
}
return 0;
}
#grid acid
#include<iostream>
using namespace std;
#define INF 1e9
int N, M;
int Xstart, Ystart;
int arr[3001][3001];
int time_[3001][3001];
int Q[1000000][3];
int front, rear;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int visited[3001][3001];
int cntNearEmpty = 0;
int cntStone;
int bfs(int row, int col){
front = rear = 0;
Q[rear][0] = row;
Q[rear][1] = col;
Q[rear++][2] = 1;
time_[row][col] = 1;
int t;
while(front!= rear){
int hang = Q[front][0];
int cot = Q[front][1];
t = Q[front++][2];
for (int i = 0; i < 4; i++)
{
int x = hang+dx[i];
int y = cot+dy[i];
if(x<0 || x >= N || y < 0 || y >= M){
continue;
}
else{
if(time_[x][y] == INF && arr[x][y] != 0){
if(arr[x][y] == 2){
cntNearEmpty++;
if(cntNearEmpty == 4){
Q[rear][0] = x;
Q[rear][1] = y;
Q[rear++][2] = t;
time_[x][y] = t;
}
}
else{
Q[rear][0] = x;
Q[rear][1] = y;
Q[rear++][2] = t+1;
time_[x][y] = t+1;
}
}
}
}
}
if(rear >= N*M-cntStone){
return t;
}
else return -1;
}
int main()
{
int tc;
int T;
int xEmpty, yEmpty;
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; ++tc)
{
cin >> N >> M;
cin >> Xstart >> Ystart;
cntStone = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> arr[i][j];
if(arr[i][j] == 2){
xEmpty = i;
yEmpty = j;
}
if(arr[i][j] == 0){
cntStone++;
}
time_[i][j] = INF;
}
}
cntNearEmpty = 0;
int cnt = bfs(Xstart-1, Ystart-1);
cout << "Case #" << tc << endl;
if(time_[xEmpty][yEmpty] == INF){
cout << -1 << " " << -1 << endl;
}
else{
cout << time_[xEmpty][yEmpty] << " " << cnt << endl;
}
}
return 0;
}
#8queen
#include<iostream>
using namespace std;
const int N = 8;
int score[N][N];
bool pos[N];
int maxScore;
int t, k;
bool dialg1[2*N], dialg2[2*N];
void initArray(){
for(int i=0; i<N; i++){
pos[i] = false;
}
for(int i=0; i<2*N; i++){
dialg1[i] = false;
dialg2[i] = false;
}
}
void backtrack(int row, int curScore){
if(row == N){
maxScore = max(maxScore, curScore);
return;
}
for(int c=0; c<N; c++){
if(!pos[c] && !dialg1[row - c + N -1] && !dialg2[row+c]){
pos[c] = dialg1[row-c + N -1] = dialg2[row+c] = true;
backtrack(row+1, curScore + score[row][c]);
pos[c] = dialg1[row-c + N -1] = dialg2[row+c] = false;
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>k;
cout<<"Case #"<<tc<<endl;
for(int x=0; x<k; x++){
for(int i=0; i<8; i++){
for(int j=0; j<8; j++){
cin>>score[i][j];
}
}
initArray();
maxScore =0;
backtrack(0, 0);
cout<<maxScore<<endl;
}
}
return 0;
}
#air plane
#include<iostream>
using namespace std;
int m =5, tc, t, i, j, n, a[26][6];
int dy[3] = {-1, 0, 1};
int tx, ty, check;
int max1;
int res;
int bomX[6][6];
bool canReach;
void DFS(int x, int y, int curCoin){
if(x==0 && max1 < curCoin){
max1 = curCoin;
}
int k;
for(k=0; k<3; k++){
tx = x -1;
ty = y + dy[k];
if(tx >= 0 && ty >=0 && ty < n){
if(a[tx][ty] !=2){
DFS(tx, ty, curCoin + a[tx][ty]);
}else{
if(curCoin <= 0 && check && a[tx][ty] == 2){
res = -1;
}
if(check){
check =0;
for(int z = max(0, tx -2); z <= min(m-1, tx+2); z++){
for(int v = max(0, ty -2); v<= min(n-1, ty+2); v++){
if(a[z][v] == 2){
bomX[z][v] = a[z][v];
a[z][v] = 0;
}
}
}
DFS(tx, ty, curCoin);
for(int z = max(0, tx -2); z <= min(m-1, tx+2); z++){
for(int v = max(0, ty -2); v<= min(n-1, ty+2); v++){
if(bomX[z][v] == 2){
a[z][v] = bomX[z][v];
}
}
}
check = 1;
}else{
DFS(tx, ty, curCoin - 1);
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>> t;
for(tc =1 ;tc <= t; tc++){
cin>> n;
for(i=0; i<n; i++){
for(j =0; j<m; j++){
cin>>a[i][j];
bomX[i][j] =0;
}
}
check = 1;
max1 = -1;
DFS(n, 2, 0);
res = 0;
if(res == -1){
cout<<"#"<<tc<<" "<<res<<endl;
}else{
cout<<"#"<<tc<<" "<<max1<<endl;
}
}
return 0;
}
#arraygame
#include<iostream>
using namespace std;
int t, n;
int a[1000000];
long long total;
int res;
int dem;
void backtrack(int s, int e, long long sum){
if(sum%2 !=0) return;
long long temp =0;
for(int i = s; i<e; i++){
temp = temp + a[i];
if(temp > sum/2){
return;
}
else if(temp == sum/2){
dem++;
if(dem > res){
res = dem;
}
backtrack(s, i, sum/2);
backtrack(i+1, e, sum/2);
dem--;
break;
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc =1; tc<=t; tc++){
cin>>n;
total =0;
res=0;
dem =0;
for(int i=0; i<n; i++){
cin>>a[i];
total+= a[i];
}
if (total %2 !=0) cout<<0<<endl;
else if(total ==0) cout<<n-1<<endl;
else{
backtrack(0, n-1, total);
cout<<res<<endl;
}
}
return 0;
}
#baovenongtrang
#include<iostream>
using namespace std;
int t, n, m;
bool isHill;
int a[701][701];
int visited[701][701];
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 x, int y){
visited[x][y] =1;
for(int k=0; k<8; k++){
int tx, ty;
tx = x + dx[k];
ty = y + dy[k];
if(tx>=0 && tx <n && ty>=0 && ty<m){
if(isHill && a[tx][ty]> a[x][y]) isHill = false;
if(a[tx][ty] == a[x][y] && !visited[tx][ty]){
//visited[tx][ty] =1;
DFS(tx, ty);
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>> t;
for(int tc=1; tc<=t; tc++){
cin>> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>a[i][j];
visited[i][j] =0;
}
}
int res =0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!visited[i][j]){
isHill = true;
DFS(i, j);
if(isHill) res ++;
}
}
}
cout<<"#"<<tc<<" "<<res<<endl;
}
return 0;
}
#cleaning robot
#include<conio.h>
#include<iostream>
//code 100/100
using namespace std;
int tc, M,N, mt[101][101], visited[101][101]; //0 clean, 1 dirty, 2 obstacle, 3 robot
int ans,cnt, dty;
int com[11][2]; //mảng lưu tọa độ robot và dirty
int QX[1000001],QY[1000001];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dis[11][11],VS[11],select[11],head, tail;
bool issafe(int x, int y){
if(x>=0 && x<M && y>=0 && y<N) return true;
else return false;
}
void init(){
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
visited[i][j]=654321;
}
}
}
void bfs(int x, int y){
head=tail=-1;
visited[x][y]=0;
QX[++tail]=x; QY[tail]=y;
while(head!=tail){
x=QX[++head]; y=QY[head];
for(int z=0;z<4;z++){
int nx=x+dx[z];
int ny=y+dy[z];
if(issafe(nx,ny) && mt[nx][ny]!=2 && visited[nx][ny]>visited[x][y]+1){
QX[++tail]=nx; QY[tail]=ny;
visited[nx][ny]=visited[x][y]+1;
}
}
}
}
void bt(int idx, int sum){
if(idx==dty+1){
if(ans>sum){
ans=sum;
return;
}
}
if(sum>ans) return;
for(int i=1;i<=dty;i++){
if(VS[i]==0){
VS[i]=1;
select[idx]=i;
bt(idx+1, sum+dis[select[idx-1]][i]);
VS[i]=0;
}
}
}
int main(){
freopen("input.txt","r", stdin);
cin>>tc;
for(int t=1;t<=tc;t++){
cin>>M>>N;
cout<<"Case #"<<t<<endl;
dty=0;
int x_rb, y_rb;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cin>>mt[i][j];
if(mt[i][j]==3) { // robot
x_rb=i; y_rb=j;
com[0][0]=i;
com[0][1]=j;
}
if(mt[i][j]==1) { // dirty
dty++;
com[dty][0]=i;
com[dty][1]=j;
}
}
}
bool check=true;
for(int m=0;m<=dty;m++){
init(); // khởi tạo mảng thăm
bfs(com[m][0], com[m][1]);
for(int k=1;k<=dty;k++){
dis[m][k]=visited[com[k][0]][com[k][1]];
if(visited[com[k][0]][com[k][1]]==654321) {
check=false;
m=dty+1;
break;
}
}
}
ans=6543210;
for(int i=0;i<11;i++){
select[i]=VS[i]=0;
}
if(check==false) cout<<-1<<endl;
else{
bt(1,0);
cout<<ans<<endl;
}
}
getch();
return 0;
}
#flatten
#include<iostream>
using namespace std;
int tc, i, dump, a[100], maxx, minx,iMax, iMin;
int main(){
freopen("input.txt", "r", stdin);
for(tc=0; tc<10; tc++){
cin>>dump;
for(i=0;i<100; i++){
cin>>a[i];
}
while(dump>0){
maxx = minx = a[0];
iMax= iMin =0;
for(i=0; i<100; i++){
if(maxx<a[i]){
maxx = a[i];
iMax =i;
}
if(minx>a[i]){
minx = a[i];
iMin =i;
}
}
a[iMax]--;
a[iMin]++;
dump--;
}
for(i=0; i<100; i++){
if(maxx<a[i]){
maxx = a[i];
}
if(minx>a[i]){
minx = a[i];
}
}
cout<<"#"<<tc+1<<" "<<maxx-minx<<endl;
}
return 0;
}
#find cycle
#include<iostream>
using namespace std;
int t, n, m;
int adj[1001][1001];
bool visited[1001];
bool reStack[1001];
bool isCycleUlti(int v){
if(!visited[v]){
visited[v]=true;
reStack[v] = true;
for(int i=1; i<=n; i++){
if(adj[v][i]){
if(!visited[i] && isCycleUlti(i)){
return true;
}else if(reStack[i]) return true;
}
}
}
reStack[v] = false;
return false;
}
bool isCycle(){
for(int i=1; i<=n; i++){
visited[i] = false;
reStack[i]= false;
}
for(int i=1; i<=n; i++){
if(!visited[i]){
if(isCycleUlti(i)){
return true;
}
}
}
return false;
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
adj[i][j] = 0;
}
}
for(int i = 1; i<=m; i++){
int u, v;
cin>>u>>v;
adj[u][v]++;
u--;
v--;
//adj[v][u]++;
}
/*int count =0;
for(int i=1; i<=m; i++){
for(int j=1; j<=m; j++){
if(adj[i][j] != 0 && adj[j][i] != 0 && adj[i][j] == adj[j][i]) count ++;
}
}
int res =0;
if(count/2 == m) res = 1;
cout<<"Case #"<<tc<<endl;
cout<<res<<endl;*/
if(isCycle()){
cout<<"Case #"<<tc<<endl;
cout<<1<<endl;
}else{
cout<<"Case #"<<tc<<endl;
cout<<0<<endl;
}
}
return 0;
}
#finding node
#include <iostream>
using namespace std;
int arr[100][2], visit[100];
bool Ans;
int st[202];
int top;
void DFS(int n) {
st[0]=n;
top=0;
while (top >= 0) {
int id = st[top--];
visit[id] = 1;
for (int i = 0; i < 2; i++) {
if (Ans)
return;
if (arr[id][i] == 99) {
Ans = true;
return;
}
if (arr[id][i] != -1 && visit[arr[id][i]] == 0) {
st[++top] = arr[id][i];
}
}
}
}
int main() {
freopen("input.txt", "r", stdin);
int tc, N;
int s, d;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 100; j++) {
arr[j][0] = arr[j][1] = -1;
visit[j] = 0;
}
cin >> tc >> N;
for (int j = 0; j < N; j++) {
cin >> s >> d;
if (arr[s][0] == -1) {
arr[s][0] = d;
} else
arr[s][1] = d;
}
Ans = false;
DFS(0);
cout << "#" << tc << " " << Ans << endl;
}
return 0;
}
#hugo dao vang 2
#include<iostream>
using namespace std;
const int MAX = 25;
const int INF = 1e9;
int n,g;
int grid[MAX][MAX];
int goldX[MAX], goldY[MAX];
//int gold[MAX][MAX];
int qX[10000000], qY[10000000];
int frontX, frontY, rearX, rearY;
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dist[MAX][MAX];
void initQueue(){
frontX = frontY = rearX = rearY = -1;
}
int isEmpty(){
return frontX== rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
int bfs(int startX, int startY){
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
dist[i][j] = INF;
}
}
initQueue();
enQueue(startX, startY);
dist[startX][startY] = 0;
while(!isEmpty()){
int pX = deQueueX();
int pY = deQueueY();
for(int i=0; i<4; ++i){
int newX = pX + directions[i][0];
int newY = pY + directions[i][1];
if(newX>=0 && newX<n && newY>=0 && newY<n && grid[newX][newY] ==1 && dist[newX][newY] == INF){
dist[newX][newY] = dist[pX][pY] +1;
enQueue(newX, newY);
}
}
}
int maxDist = 0;
for(int i=0; i<g; ++i){
int goldDist = dist[goldX[i]][goldY[i]];
if(goldDist == INF) return INF;
maxDist = max(maxDist, goldDist);
}
return maxDist;
}
int main(){
freopen("input.txt", "r", stdin);
int t;
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n>>g;
for(int i=0; i<g; ++i){
cin>>goldX[i]>>goldY[i];
goldX[i]--;
goldY[i]--;
}
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
cin>>grid[i][j];
}
}
int minMaxDist = INF;
int maxGold =0;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(grid[i][j] == 1){
bool isGold = false;
for(int k=0; k<g; ++k){
if(i == goldX[k] && j == goldY[k]){
isGold = true;
break;
}
}
if(!isGold)
{
int maxDist = bfs(i,j);
minMaxDist = min(minMaxDist, maxDist);
}
}
}
}
if(minMaxDist == INF){
cout<<"Case #"<<tc<<endl;
cout<<-1<<endl;
}else{
cout<<"Case #"<<tc<<endl;
cout<<minMaxDist<<endl;
}
}
return 0;
}
#hugo ban dau
#include <iostream>
using namespace std;
const int dir[4][4] = {
{1, 2, 5, 6},
{1, 3, 6, 7},
{1, 2, 4, 7},
{1, 3, 4, 5},
};
const int type[8][4] = {
{},
{1, 1, 1, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1}
};
const int dX[] = {-1, 0, 1, 0};
const int dY[] = {0, 1, 0, -1};
int frontX, frontY, rearX, rearY, t, n, m, map[60][60], p, visited[60][60], res;
int qX[1000001], qY[1000001];
bool map_dir[10][10];
void initQueue(){
frontX = rearX = frontY = rearY = -1;
}
bool IsEmpty(){
return frontX == rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
void BFS(int x, int y, int p){
initQueue();
enQueue(x, y);
visited[x][y] = 1;
while (!IsEmpty()){
int curX = deQueueX();
int curY = deQueueY();
if (visited[curX][curY] > p){
continue;
}
for (int index = 0; index < 4; index++){
int pipedir = type[map[curX][curY]][index];
if (pipedir == 0) continue;
int tx = curX + dX[index];
int ty = curY + dY[index];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] != 0 && visited[tx][ty] == -1) {
if (map_dir[index][map[tx][ty]] == 1){
visited[tx][ty] = visited[curX][curY] + 1;
enQueue(tx, ty);
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin >> t;
for (int tc = 1; tc <= t; tc++){
int hugoX, hugoY;
cin >> n >> m >> hugoX >> hugoY >> p;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> map[i][j];
visited[i][j] = -1;
}
}
for (int i = 0; i < 10; i++){
for (int j = 0; j < 10; j++) map_dir[i][j] = 0;
}
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) map_dir[i][dir[i][j]] = 1;
BFS(hugoX,hugoY, p);
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++){
if (visited[i][j] <= p && visited[i][j] > 0) cnt ++;
}
}
cout << "Case #" << tc << endl;
cout << cnt << endl;
}
return 0;
}
#icecave
#include<iostream>
using namespace std;
int t, n, m, r1, c1, r2, c2;
char a[1001][1001];
int visited[1001][1001];
int qX[1000001], qY[1000001];
int frontX, frontY, rearX, rearY;
int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool flag;
void initQueue(){
frontX = frontY = rearX = rearY = -1;
}
bool isEmty(){
return frontX == rearX;
}
void enQueue(int x, int y){
rearX++;
rearY++;
qX[rearX] = x;
qY[rearY] = y;
}
int deQueueX(){
frontX++;
return qX[frontX];
}
int deQueueY(){
frontY++;
return qY[frontY];
}
void BFS(int x, int y, int s, int e){
initQueue();
visited[x][y] = 1;
enQueue(x, y);
while(!isEmty()){
int curX = deQueueX();
int curY = deQueueY();
for(int k=0; k<4; k++){
int tempX = curX + directions[k][0];
int tempY = curY + directions[k][1];
if(tempX>=0 && tempX<n && tempY>=0 && tempY<m){
if(tempX == s && tempY == e){
if(a[s][e] == '0'){
//a[s][e] = '-1';
flag = true;
return;
}
}
if(a[tempX][tempY] == '1' ){
visited[tempX][tempY] = 1;
enQueue(tempX, tempY);
a[tempX][tempY] = '0';
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n>>m;
cin>>r1>>c1>>r2>>c2;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>a[i][j];
}
}
flag = false;
BFS(r1, c1, r2, c2);
if(flag){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}
#qua cau
#include<iostream>
using namespace std;
int m =5, tc, t, i, j, n, a[20][6];
//int dx[3] = {-1,-1, -1};
int dy[3] = {-1, 0, 1};
int tx, ty, check;
int max1;
void DFS(int x, int y, int curCoin){
if(x==0 && max1 < curCoin){
max1 = curCoin;
}
int k;
for(k =0; k<3; k++){
tx = x - 1;
ty = y + dy[k];
if(tx>=0 && ty>=0 && ty<5){
if(a[tx][ty] != 2){
DFS(tx, ty, curCoin + a[tx][ty]);
}else{
if(check){
check=0;
DFS(tx, ty, curCoin);
check = 1;
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
cin>> t;
for(tc =1 ;tc <= t; tc++){
cin>> n;
for(i=0; i<n; i++){
for(j =0; j<m; j++){
cin>>a[i][j];
}
}
check = 1;
max1 = -1;
DFS(n, 2, 0);
cout<<"#"<<tc<<" "<<max1<<endl;
}
return 0;
}
#well project
#include<iostream>
using namespace std;
#define INF 1000000
int t, n, a[1001][1001], visited[1001], tc;
int minNode(int keyval[], bool mstSet[], int n){
int mini = INF;
int min_index;
for(int i=0; i<n; i++){
if(!mstSet[i] && keyval[i]< mini){
mini = keyval[i];
min_index = i;
}
}
return min_index;
}
int findMin(int a[][1001], int n){
int parent[1001];
int keyval[1001];
bool mstSet[1001];
for(int i=0; i<n; i++){
keyval[i] = INF, mstSet[i] = false;
}
keyval[0] =0;
parent[0]= -1;
for(int count =0; count<n-1; count ++){
int u =minNode(keyval, mstSet, n);
if(keyval[u] == INF) return -1;
mstSet[u] = true;
for(int i=0; i<n; i++){
if(a[u][i] !=INF && !mstSet[i] && a[u][i]< keyval[i]){
parent[i] = u;
keyval[i] = a[u][i];
}
}
}
int minCost =0;
for(int i=1; i<n;i++){
minCost +=a[i][parent[i]];
}
return minCost;
}
int main(){
freopen("input.txt", "r", stdin);
cin>>t;
for(tc=1; tc<=t; tc++){
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>a[i][j];
}
}
int res =0;
res = findMin(a, n);
cout<<"Case #"<<tc<<endl;
cout<<res<<endl;
}
return 0;
}
#pizza location
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
// Nhức cái đầu luôn // code ok
const int MAX_PLACE = 20;
const int MAX_HOUSE = 101;
int numRest; //số nhà hàng
int R; //bán kính giao hàng
int numPlace; //số slot có thể lựa chọn
int XPlace[MAX_PLACE], YPlace[MAX_PLACE]; //tọa độ slot
int numHouse; //số nhà dân
int XHouse[MAX_HOUSE], YHouse[MAX_HOUSE]; //tọa độ nhà dân
int numPeople[MAX_HOUSE];//số người trong nhà
int maxPeo; //max người có thể phục vụ
int sumPeo; //tổng số người
int Reach[MAX_PLACE][MAX_HOUSE]; //lưu vị trí nhà dân mà slot có thể phục vụ ở từng slot
int Count[MAX_PLACE]; //đếm có bao nhiêu ngôi nhà được phục vụ tại mỗi slot
int PRest[MAX_PLACE]; //mảng lưu lại vị trí đã đặt của các nhà hàng
void BT(int pos, int numIgnore, int sumRes){ // slot,vị trí ko đặt ,tổng nhà hàng
if(pos == numPlace){
int serPeople = 0;
int VS[MAX_HOUSE] = {0};
for(int i = 0; i < numRest; i++){ // tính tổng số người có thể phục vụ với số lượng nhà hàng phù hợp
int idRest = PRest[i];
for(int j = 0; j < Count[idRest]; j++){ // thăm từng slot một để tính tổng người
int idHouse = Reach[idRest][j];
if(VS[idHouse] == 0){
VS[idHouse] = 1;
serPeople += numPeople[idHouse];
}
if(serPeople == sumPeo) break;// nếu số người = max thì thoát
}
}
if(serPeople > maxPeo){
maxPeo = serPeople;
}
return;
}
if(maxPeo == sumPeo) return;
if(sumRes < numRest){ //đặt nhà hàng vào các vị trí
PRest[sumRes] = pos;
BT(pos + 1,numIgnore,sumRes + 1);
if(maxPeo == sumPeo) return;
}
if(numIgnore < numPlace - numRest){ //không đặt nhà hàng vào các vị trí đó
BT(pos+1,numIgnore + 1,sumRes);
}
}
int main(){
freopen("input.txt", "r", stdin);
int T; cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> numRest >> R;
cin >> numPlace;
for(int i = 0; i < numPlace; i++){
cin >> XPlace[i] >> YPlace[i];
}
sumPeo = maxPeo = 0;
cin >> numHouse;
for(int i = 0; i < numHouse; i++){
cin >> XHouse[i] >> YHouse[i] >> numPeople[i];
sumPeo += numPeople[i];
Count[i] = 0;
}
// lưu lại mỗi slot phục vụ được những nhà dân nào
for(int i = 0; i < numPlace; i++){
for(int j = 0; j < numHouse; j++){
int temp = (XPlace[i] - XHouse[j])*(XPlace[i] - XHouse[j])
+(YPlace[i] - YHouse[j])*(YPlace[i] - YHouse[j]);
if(temp <= R * R){
Reach[i][Count[i]] = j;
Count[i]++;
}
}
}
BT(0,0,0);
cout << "#" << tc << " " << maxPeo << endl;
}
return 0;
}
#hugo giao hang
#include <iostream>
using namespace std;
int Sx, Sy, Hx, Hy;
int tc;
int N;
int pizaX[11];
int pizaY[11];
int mark[11];
int curDis = 0;
void init()
{
for (int i=0; i<=10; i++)
mark[i] = 0;
curDis = 10000000000;
}
int mABS(int a, int b)
{
if (a > b) return a - b;
else return b - a;
}
void backtracking (int index, int total, int cx, int cy)
{
if (index == N)
{
if (curDis > total + mABS(cx,Hx) + mABS(cy,Hy))
curDis = total + mABS(cx,Hx) + mABS(cy,Hy);
}
else
for (int i=0; i< N ; i++)
{
if (mark[i] == 0 && total + mABS(cx,pizaX[i]) + mABS(cy,pizaY[i]) <= curDis)
{
mark[i] = 1;
backtracking(index + 1, total + mABS(cx,pizaX[i]) + mABS(cy,pizaY[i]), pizaX[i],pizaY[i]);
mark[i] = 0;
}
}
}
int main()
{
// freopen ("input.txt", "r", stdin);
cin >> tc;
for (int t=1; t <= tc; t++)
{
cin >> Sx >> Sy >> Hx >> Hy ;
cin >> N;
for (int i=0; i<N; i++)
{
cin >> pizaX[i] >> pizaY[i];
}
init();
backtracking(0,0,Sx,Sy);
cout << "Case #" << t << " " << curDis << endl;
}
return 0;
}
#little elephant
#include<iostream>
using namespace std;
int N,K ,M;
int R[18];
int visited[18];
int ans ;
int cnt;
void inp()
{
cin>> N >> K >> M;
for (int i = 0; i < N; i++)
{
cin >> R[i];
}
}
int findMax(int idx)
{
int maxElep = 0;
for (int i = idx; i < idx + K; i++)
{
maxElep = max(maxElep, R[i]);
}
return maxElep;
}
bool check()
{
for (int i = 0; i < N-K+1; i++)
{
int maxElep = findMax(i);
int temp = 0;
for (int j = i; j < i + K; j++)
{
if(maxElep == R[j]) temp++;
}
if (temp >= M)
{
return false;
}
}
return true;
}
void BT(int idx)
{
if(M == 1){
return;
}
if (cnt > ans)
{
return;
}
if (idx > N)
{
//ans = min(ans,cnt);
return;
}
if(check()){
ans = min(ans,cnt);
return;
}
else
{
BT(idx + 1);
R[idx] +=1;
cnt++;
BT(idx + 1);
R[idx] -= 1;
cnt--;
}
}
int main()
{
freopen("Text.txt","r",stdin);
int T;
cin>> T;
for (int tc = 1; tc <= T; tc++)
{
inp();
ans = 10000000;
cnt =0;
BT(0);
if (ans == 10000000)
{
cout<<"#"<<tc<<" " << -1 <<endl;
}
else
{
cout <<"#"<<tc<<" "<< ans <<endl;
}
}
return 0;
}
#hugo ve nha
#include <iostream>
using namespace std;
#define MAX_N 21
#define INF 1000000000
// code mentor1 100/100
int money[MAX_N];
int warrior[MAX_N];
int N;
int teammate[MAX_N];
int old, fresh;
int minCost;
void go(int i, int cost){
if (i == N) {
if (cost < minCost)
minCost = cost;
return;
}
if (cost >= minCost)
return;
go(i + 1, cost + money[i]);
teammate[fresh] += warrior[i];
go(i + 1, cost + 2 * money[i]);
teammate[fresh] -= warrior[i];
if (teammate[old] + teammate[old + 1] + teammate[fresh] >= warrior[i]) {
int remain = warrior[i];
int dead[3];
dead[0] = dead[1] = dead[2] = 0;
for (int j = old; j <= fresh; j++) {
if (remain > teammate[j]) {
remain -= teammate[j];
dead[j - old] = teammate[j];
teammate[j] = 0;
} else {
teammate[j] -= remain;
dead[j - old] = remain;
break;
}
}
old++; fresh++;
teammate[fresh] = 0;
go(i + 1, cost);
old--; fresh--;
for (int j = old; j <= fresh; j++)
teammate[j] += dead[j - old];
}
}
int main(){
freopen("input.txt", "r", stdin);
int tc, T;
cin >> T;
for (tc = 1; tc <= T; tc++) {
cin >> N;
for (int i = 0; i < N; i++){
cin >> warrior[i] >>money[i];
}
old = 0; fresh = 2;
teammate[0] = teammate[1] = teammate[2] = 0;
minCost = INF;
go(0, 0);
cout<<"#"<<tc<<" "<<minCost<<endl;
}
return 0;
}
#hugo running
#include<iostream>
using namespace std;
// CODE 100/100
int minThoigian;
int s;
int arr[5][2];
int enery;
void BT(int kieuchay, int quangduong, int thoigian, int nangluong){
if(nangluong > enery){
return;
}
if(thoigian > minThoigian){
return;
}
if(quangduong >= s){
if(thoigian < minThoigian){
minThoigian = thoigian;
}
return;
}
for (int i = kieuchay; i < 5; i++)
{
BT(i, quangduong+1, thoigian+arr[i][0], nangluong+arr[i][1]);
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
int ph, giay, e;
freopen("input50.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> enery >> s;
for (int i = 0; i < 5; i++)
{
cin >> ph >> giay >> e;
arr[i][0] = ph*60+giay;
arr[i][1] = e;
}
Answer = 0;
minThoigian = 100000;
BT(0, 0, 0, 0);
if(minThoigian != 100000){
ph = minThoigian/60;
giay = minThoigian%60;
cout << "Case #" << test_case << endl << ph << " " << giay << endl;
}else{
cout << "Case #" << test_case << endl << -1 << endl;
}
}
return 0;
}
#moi dam cuoi
#include<iostream>
// code 100/100
using namespace std;
int dinh, canh;
int u, v;
int maTranKe[101][101];
int visited[101];
int cntVisit[101];
void dfs(int d){
if(d == v){
for (int i = 1; i <= dinh; i++)
{
if(visited[i] == 1){
cntVisit[i]++;
}
}
return;
}
for (int i = 1; i <= dinh; i++)
{
if(visited[i] == 0 && maTranKe[d][i] == 1){
visited[i] = 1;
dfs(i);
visited[i] = 0;
}
}
}
int cnt_dinh(){
int cnt = 0;
for (int i = 1; i <= dinh; i++)
{
if(cntVisit[i] == cntVisit[v]){
cnt++;
}
}
return cnt-2;
}
void create(){
for (int i = 1; i <= dinh; i++)
{
for (int j = 1; j <= dinh; j++)
{
maTranKe[i][j] = 0;
}
cntVisit[i] = 0;
visited[i] = 0;
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
int d1, d2;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
cin >> dinh >> canh >> u >> v;
create();
for (int i = 0; i < canh; i++)
{
cin >> d1 >> d2;
maTranKe[d1][d2] = 1;
}
visited[u] = 1;
dfs(u);
Answer = cnt_dinh();
// Print the answer to standard output(screen).
cout << Answer << endl << endl;
}
return 0;//Your program should return 0 on normal termination.
}
#mountain walking
#include <iostream>
using namespace std;
// code 100/100
int map[100][100];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int highest, lowest;
int N;
int visitedCnt = 0;
int visited[100][100];
int Q[10000];
int front, rear;
bool hasPath(int lowBound, int highBound){
if (map[0][0] < lowBound || map[0][0] > highBound || map[N - 1][N - 1] < lowBound || map[N - 1][N - 1] > highBound)
return false;
front = rear = 0;
Q[0] = 0;
int nextR, nextC;
visited[0][0] = ++visitedCnt;
int r, c;
while (front <= rear) {
r = Q[front] / 100;
c = Q[front++] % 100;
for (int d = 0; d < 4; d++) {
nextR = r + dy[d];
nextC = c + dx[d];
if (nextR < 0 || nextR == N || nextC < 0 || nextC == N || visited[nextR][nextC] == visitedCnt)
continue;
if (map[nextR][nextC] < lowBound || map[nextR][nextC] > highBound)
continue;
if (nextR == N - 1 && nextC == N - 1)
return true;
visited[nextR][nextC] = visitedCnt;
Q[++rear] = nextR * 100 + nextC;
}
}
return false;
}
int main(){
freopen("input.txt", "r", stdin);
int T, tc;
int left, right, mid;
cin >> T;
for (tc = 1; tc <= T; tc++) {
cin >> N;
highest = 0;
lowest = 1000000000;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] < lowest) lowest = map[i][j];
if (map[i][j] > highest) highest = map[i][j];
}
}
if (lowest == highest) {
cout <<"#"<<tc<<" "<<0<<endl;
continue;
}
left = 0;
right = highest - lowest;
bool reach;
while (left <= right) {
mid = (left + right) >> 1;
reach = false;
for (int i = lowest; i <= highest - mid; i++) {
if (hasPath(i, i + mid)) {
reach = true;
break;
}
}
if (reach) right = mid - 1;
else left = mid + 1;
}
cout <<"#"<<tc<<" "<<left<<endl;
}
return 0;
}
#nga tu
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
using namespace std;
#define size 100
int n, a[size][size], b[size][size];
void updateA (){
for (int i = 1; i <= n; i++){
for (int j = 1; j <=n; j++){
if (a[i][j] != b[i][j]) a[i][j] = b[i][j];
}
}
}
int main(){
freopen("input.txt", "r", stdin);
int year = 0, i, j, x, y;
cin >> n;
for (i = 1; i <= n; i++){
for (j = 1; j <=n; j++){
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
bool haveChange = true;
while (haveChange){
haveChange = false;
for (i = 2; i < n; i++){
for (j = 2; j < n; j++){
if (a[i][j] == 0 && (a[i+1][j] + a[i-1][j] + a[i][j-1] + a[i][j+1]) == 1) {
haveChange = true;
// 4 directions
if (a[i+1][j]==1){
x=i; y=j;
while (a[++x][y]==1 && x <= n) b[x][y]=0;
}
else if (a[i-1][j]==1){
x=i; y=j;
while (a[--x][y]==1 && x >=1) b[x][y]=0;
}
else if (a[i][j+1]==1){
x=i; y=j;
while (a[i][++y]==1 && y<=n) b[x][y]=0;
}
else if (a[i][j-1] == 1){
x=i; y=j;
while (a[i][--y]==1 && y >=1) b[x][y]=0;
}
}
}
}
if (haveChange) year++;
updateA ();
}
cout <<"#"<<" "<<year;
return 0;
}
#pha huy he thong dien
#define _CRT_SECURE_NO_WARNINGS
// code 100
#include<iostream>
int arr[101][101];
int temp[101][101];
int visit[101];
int Q[100001];
int front, rear;
int N;
int cntMax;
int dao;
int cntChuTrinh;
using namespace std;
void clear(){
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= N; j++)
{
arr[i][j] = 0;
temp[i][j] = 0;
}
visit[i] = 0;
}
dao = 0;
}
void convert_dsk(){
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= N; j++)
{
temp[i][j] = arr[i][j];
}
}
}
int demchutrinh(){
for (int iD = 1; iD <= N; iD++)
{
if(visit[iD] == 0){
front = rear = 0;
Q[rear++] = iD;
visit[iD] = 1;
while(rear != front){
int dd = Q[front++];
for (int i = 1; i <= N; i++)
{
if(visit[i] == 0 && temp[dd][i] == 1){
Q[rear++] = i;
visit[i] = 1;
}
}
}
cntChuTrinh++;
}
}
return cntChuTrinh;
}
void BT(int d){
cntChuTrinh = 0;
if(d > N){
return;
}
for (int i = 1; i <= N; i++)
{
if(temp[d][i] == 1){
temp[d][i] = 0;
temp[i][d] = 0;
}
}
for (int i = 1; i <= N; i++)
{
visit[i] = 0;
}
if(demchutrinh()-1 > cntMax){
cntMax = demchutrinh();
dao = d;
}
for (int i = 1; i <= N; i++)
{
if(arr[d][i] == 1){
temp[d][i] = 1;
temp[i][d] = 1;
}
}
BT(d+1);
}
void init(){
cin >> N;
clear();
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> arr[i][j];
}
}
convert_dsk();
cntMax = demchutrinh();
BT(1);
cout << dao << endl;
}
int main()
{
int test_case;
int T;
int Answer;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
init();
}
return 0;
}
#prime ring
#include <iostream>
using namespace std;
// code 100/100
int arr[17];
bool selected[17];
int N, E;
bool isPrime[101];
void sieve(){
for (int i = 0; i < 101; i++)
isPrime[i] = true;
isPrime[0] = isPrime[1] = true;
for (int i = 2; i < 101; i++) {
if (isPrime[i])
for (int j = i * 2; j < 101; j += i)
isPrime[j] = false;
}
}
int cnt;
void go(int k, int i) {
if (k == N) {
if (isPrime[arr[0] + arr[i]])
cnt++;
return;
}
for (int j = 1; j < N; j++) {
if (!selected[j] && isPrime[arr[i] + arr[j]]) {
selected[j] = true;
go(k + 1, j);
selected[j] = false;
}
}
}
int main(){
int T, tc;
freopen("input.txt", "r", stdin);
cin >> T;
sieve();
for (tc = 1; tc <= T; tc++) {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
cnt = 0;
selected[0] = true;
go(1, 0);
cout <<"Case "<<tc<<" :"<<cnt<<endl;
}
return 0;
}
#sky tour
#include <iostream>
using namespace std;
// code 100/100
int n, e, ans;
int map[3][15];
int dx[] ={2,1,0,-1,-2};
int dy[] ={1,1,1,1,1};
void Try (int x, int y, int ene, int score) {
if (y == n) {
if (ans < score) ans = score;
return;
}
for (int i = 0; i < 5; i++) {
int x1 = x + dx[i];
int y1 = y + dy[i];
if (x1 < 0 || x1 >= 3 || y1 < 0 || y1 > n) continue;
if ((i == 0 || i == 3) && ene >= 2) {
Try(x1, y1, ene - 2, score + map[x1][y1]);
} else if (i == 1 && ene >= 1) {
Try(x1, y1, ene - 1, score + map[x1][y1]);
} else if (i == 4 && ene >= 4) {
Try(x1, y1, ene - 4, score + map[x1][y1]);
} else if (i == 2){
Try(x1, y1, ene, score + map[x1][y1]);
}
}
}
int main(){
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> e>>n;
for (int i = 0; i < 3; i++) {
for (int j = 1; j <= n; j++) {
cin >> map[i][j];
}
}
ans = 0;
Try(1, 0, e, 0);
cout <<"#"<<tc<<" "<<ans<<endl;
}
return 0;
}
#the settle of catan
#include<iostream>
using namespace std;
int N, M;
int arr[26][26];
int maxCanh = 0;
int visit[26][26];
void BT(int dinh, int cntCanh){
if(cntCanh > maxCanh){
maxCanh = cntCanh;
}
for (int i = 0; i < N; i++)
{
if(arr[dinh][i] == 1 && visit[dinh][i] == 0){
visit[dinh][i] = 1;
visit[i][dinh] = 1;
BT(i, cntCanh+1);
visit[dinh][i] = 0;
visit[i][dinh] = 0;
}
}
}
void clear_canh(){
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
visit[i][j] = 0;
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
freopen("input.txt", "r", stdin);
cin >> T;
int node1, node2;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
arr[i][j] = 0;
}
}
for (int i = 0; i < M; i++)
{
cin >> node1 >> node2;
arr[node1][node2] = 1;
arr[node2][node1] = 1;
}
maxCanh = 0;
for (int i = 0; i < N; i++)
{
clear_canh();
BT(i, 0);
}
cout << maxCanh << endl;
}
return 0;
}
#thong tri khu vuc
#include<iostream>
// code 100/100
using namespace std;
int N;
int map[105][105];
int temp[105][105];
int visit[105][105];
int cnt[6];
int dR[4] = {0, -1, 0, 1};
int dC[4] = {-1, 0, 1, 0};
struct COOR {
int r, c;
} Queue[10005], Q[10005];
int front, rear;
void init() {
front = rear = -1;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
visit[i][j] = 0;
for (int i = 1; i < 6; i++)
cnt[i] = 0;
}
void push(int r, int c) {
rear++;
Queue[rear].r = r;
Queue[rear].c = c;
}
COOR pop() {
return Queue[++front];
}
bool isEmpty() {
return front == rear;
}
void BFS1(int r, int c) {
int front1 = -1, rear1 = -1;
visit[r][c] = 1;
rear1++;
Q[rear1].r = r; Q[rear1].c = c;
cnt[map[r][c]]++;
while (front1 != rear1) {
front1++;
int topR = Q[front1].r; int topC = Q[front1].c;
for (int i = 0; i < 4; i++) {
int nR = topR + dR[i];
int nC = topC + dC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < N && !visit[nR][nC]) {
if (map[nR][nC] == map[topR][topC]) {
visit[nR][nC] = 1;
rear1++;
Q[rear1].r = nR; Q[rear1].c = nC;
cnt[map[nR][nC]]++;
}
}
}
}
}
void BFS(int r, int c) {
init();
visit[r][c] = 1;
push(r, c);
while (!isEmpty()) {
COOR coor = pop();
for (int i = 0; i < 4; i++) {
int nR = coor.r + dR[i];
int nC = coor.c + dC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < N && !visit[nR][nC]) {
if (temp[nR][nC] == 0) {
visit[nR][nC] = 1;
push(nR, nC);
} else {
BFS1(nR, nC);
}
}
}
}
}
void BFS2(int r, int c) {
visit[r][c] = 1;
push(r, c);
while (!isEmpty()) {
COOR coor = pop();
for (int i = 0; i < 4; i++) {
int nR = coor.r + dR[i];
int nC = coor.c + dC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < N && !visit[nR][nC]) {
if (temp[nR][nC] == temp[coor.r][coor.c]) {
visit[nR][nC] = 1;
push(nR, nC);
}
}
}
}
}
int findMax() {
int m = -1;
int idx = 0;
for (int i = 1; i < 6; i++) {
if (cnt[i] >= m) {
m = cnt[i];
idx = i;
}
}
return idx;
}
int main() {
int T;
//freopen("sample_input.txt", "r", stdin);
cin >> T;
for (int test_case = 1; test_case <= T; ++test_case) {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
temp[i][j] = map[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (temp[i][j] == 0) {
BFS(i, j);
int val = findMax();
for (int i = 0; i <= rear; i++) {
temp[Queue[i].r][Queue[i].c] = val;
}
}
}
}
init();
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
BFS2(i, j);
ans++;
}
}
}
cout << "Case #" << test_case << endl << ans << endl;
}
return 0;
}
#tiet kiem dien
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
// code 100/100
using namespace std;
int N, K;
int state[105];
int ans;
void action(int key) {
int n = 0;
int k = key + 1;
while ((k + n*(k+1)) <= N) {
state[k + n*(k+1)] = 1 - state[k + n*(k+1)];
n++;
}
}
void BT(int k, int time) {
if (k == K || time == 3) {
int cnt = 0;
for (int i = 1; i <= N; i++)
if (!state[i])
cnt++;
if (cnt > ans)
ans = cnt;
return;
}
for (int i = 0; i < 2; i++) {
if (i == 0) {
BT(k + 1, time);
} else {
action(k);
BT(k + 1, time + 1);
action(k);
}
}
}
int main() {
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; ++tc) {
cin >> N >> K;
for (int i = 1; i <= N; i++)
cin >> state[i];
ans = 0;
BT(0, 0);
cout << "#" << tc << " " << ans << endl;
}
return 0;
}
#tuan trang mat
#include <iostream>
using namespace std;
// code 100/100
int dske[1001][1001];
int cost_board[1001][1001];
int visit[1000000];
int nVertex, nEdge, nK_VS;
int Need_VS[20];
int Need_Mark[20];
int res;
int pay_board[1001][1001];
void input(){
cin >> nVertex >> nEdge >> nK_VS;
for(int i = 1; i <= nK_VS; i++){
cin >> Need_VS[i];
}
Need_VS[0] = 1;
for(int i = 1; i <= nVertex; i++){
dske[i][0] = 0;
}
for(int i = 1; i <= nVertex; i++){
for(int j = 1; j <= nVertex; j++){
cost_board[i][j] = 9999999;
}
}
for(int i = 0; i < nEdge; i++){
int v1, v2, cost;
cin >> v1 >> v2 >> cost;
dske[v1][0]++;
dske[v1][dske[v1][0]] = v2;
cost_board[v1][v2] = cost;
}
}
void dfs(int st, int v1, int v2, int _cost){
if(v1 == v2){
if(_cost < pay_board[st][v2])
pay_board[st][v2] = _cost;
return;
}
if(_cost > pay_board[st][v2])
return;
visit[v1] = 1;
int nAdj = dske[v1][0];
for(int i = 1; i <= nAdj; i++){
int v_cur = dske[v1][i];
if(visit[v_cur] == 0){
dfs(st,v_cur, v2, _cost + cost_board[v1][v_cur]);
}
}
visit[v1] = 0;
}
void dijisktra(int s){
for(int i = 1; i <= nVertex; i++){
pay_board[s][i] = 9999999;
visit[i] = 0;
}
pay_board[s][s] = 0; // khoi tao gt ban dau
for(int i = 1; i <= nVertex; i++){
int uBest = -1;
int minVal = 9999999;
//tim dinh chua xet co d min
for(int u = 1; u <= nVertex; u++){
if(pay_board[s][u] < minVal && visit[u] == 0){
uBest = u;
minVal = pay_board[s][u];
}
}
// update duong di
int u = uBest;
visit[u] = 1;
for(int v = 1; v <= nVertex; v++){
int temp = pay_board[s][u] + cost_board[u][v];
if(pay_board[s][v] > temp ){
pay_board[s][v] = temp;
}
}
}
}
void calc_min_cost(){
for(int i = 0; i <= nK_VS; i++){
/*for(int j = 0; j <= nK_VS; j++){
if(i == j) pay_board[Need_VS[i]][Need_VS[j]] = 0;
else{
pay_board[Need_VS[i]][Need_VS[j]] = 9999999;
dfs(Need_VS[i],Need_VS[i],Need_VS[j],0);
}
}*/
dijisktra(Need_VS[i]);
}
}
void back_track(int idx, int nVisited, int _cost){
if(nVisited >= nK_VS){
int temp_cost = _cost;
if(pay_board[Need_VS[idx]][1] != 9999999){
temp_cost = temp_cost + pay_board[Need_VS[idx]][1];
if(temp_cost < res)
res = temp_cost;
}
return;
}
if(_cost > res)
return;
Need_Mark[idx] = 1;
for(int i = 1; i <= nK_VS; i++){
if(Need_Mark[i] == 0 && pay_board[Need_VS[idx]][Need_VS[i]] != 9999999){
back_track(i, nVisited + 1, _cost + pay_board[Need_VS[idx]][Need_VS[i]]);
}
else{
continue;
}
}
Need_Mark[idx] = 0;
}
int main(){
freopen("input1.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
input();
//if(tc != 6)
calc_min_cost();
res = 9999999;
back_track(0,0,0);
cout << "Case #" << tc << endl;
if(res != 0)
cout << res << endl << endl;
else
cout << -1<< endl << endl;
}
return 0;
}
#uniform distribution
#include<iostream>
int N;
int arr[6][6];
int visited[6][6];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
using namespace std;
int Q[100][2];
int front, rear;
int cnt;
void bfs(int row, int col){
front = rear = 0;
Q[rear][0] = row;
Q[rear++][1] = col;
visited[row][col] = 1;
cnt++;
while(front != rear){
int r = Q[front][0];
int c = Q[front++][1];
for (int i = 0; i < 4; i++)
{
int x = r+dx[i];
int y = c+dy[i];
if(x >=0 && x < N && y >=0 && y < N && visited[x][y] == 0 && arr[x][y] == arr[row][col]){
Q[rear][0] = x;
Q[rear++][1] = y;
visited[x][y] = 1;
cnt++;
}
}
}
}
int check_arr(){
int area = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if(visited[i][j] == 0){
area++;
bfs(i, j);
if(area == 5){
if(cnt < N*N){
return 0;
}
else{
return 1;
}
}
}
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
int x, y;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
int num = 1;
cnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
arr[i][j] = 5;
visited[i][j] = 0;
}
}
for (int i = 0; i < N-1; i++)
{
for (int j = 0; j < N; j++)
{
cin >> x >> y;
arr[x-1][y-1] = num;
}
num++;
}
int c = check_arr();
cout << "Case #" << test_case << endl;
if(c==1){
cout << "good" << endl;
}
else{
cout << "wrong" << endl;
}
}
return 0;
}
#validate the maze
#include<iostream>
using namespace std;
char map[25][25];
int Gate[100][2];
int N, M;
int x_start, y_start, x_end, y_end;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
bool check(int x, int y){
return (x>=0 && x<N && y>=0 && y<M);
}
void Try(int x, int y, bool &ans){
for(int i=0; i<4; i++){
int x_next = x + dx[i];
int y_next = y + dy[i];
if(check(x_next, y_next)){
if(x_next == x_end && y_next == y_end) {
ans=true;
return;
}
else if(map[x_next][y_next] == '.') {
map[x_next][y_next] = '#';
Try(x_next, y_next, ans);
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
int T; cin>>T;
for(int tc=1; tc<=T; tc++){
cin>>N>>M;
int dem = 0;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin>>map[i][j];
if((i==0 || i==N-1 || j==0 || j==M-1) && map[i][j]=='.'){
dem++;
Gate[dem][0] = i;
Gate[dem][1] = j;
}
}
}
x_start = Gate[1][0];
y_start = Gate[1][1];
x_end = Gate[2][0];
y_end = Gate[2][1];
bool ans = false;
Try(x_start, y_start, ans);
//cout<<dem<<endl;
if(dem==2 && ans){
cout<<"valid"<<endl;
}
else cout<<"invalid"<<endl;
}
return 0;
}
#visit departments
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
//code 100/100
using namespace std ;
int n , e , k , time1 ;
int A[110][101];
float xs[101][101] ;
float P[101][101] ;
int max(int t)
{
int max1 = 0 ;
for(int i = 1 ; i <= n ; i++ )
{
if(P[i][t] > P[max1][t])
{
max1 = i ;
}
}
for(int i = 1 ; i <= n ; i++ )
{
if(P[i][t] == P[max1][t])
{
if(max1 > i)
{
max1 = i ;
}
}
}
return max1 ;
}
int main()
{
//freopen("input.txt" , "r" , stdin) ;
for(int tc = 1 ; tc <= 10 ; tc ++)
{
cin >> n >> e >> k >> time1 ;
for(int i = 1 ; i <= 101 ; i++ )
{
for(int j = 1 ; j <= 101 ; j++ )
{
P[i][j] = 0 ;
A[i][j] = 0 ;
xs[i][j] = 0 ;
}
}
for(int i = 0 ; i < e ; i++)
{
int x , y ;
float xs1;
cin >> x >> y ;
scanf("%f",&xs1);
xs[x][y] = 0 ;
A[x][0] ++ ;
A[x][A[x][0]] = y ;
xs[x][y] = (float)xs1 ;
}
int t = 1 ;
P[1][1] = 1 ;
while(t <= (time1/10))
{
for(int i = 1 ; i <= n ; i++)
{
if(P[i][t] != 0)
{
for(int j = 1 ; j <= A[i][0]; j++)
{
P[A[i][j]][t+1] += P[i][t] * xs[i][A[i][j]];
}
}
}
t++ ;
}
int kq1 = max(t) ;
int kq2 = max((time1- k)/10 + 1);
printf("#%d %d %.6lf %d %.6lf" , tc,kq1,P[kq1][t] ,kq2, P[kq2][(time1- k)/10 + 1] );
//cout << "#" << tc << " " << kq1 << " " << << " " << kq2 <<" " <<<< endl ;
cout << endl ;
}
return 0 ;
}
#bieu thuc zero
#include<iostream>
int arr[51];
int N;
int visited[51];
int cnt;
using namespace std;
enum dau{
TRU = 1,
CONG,
GOP
};
void arr_(){
for (int i = 0; i <= N; i++)
{
arr[i] = i;
visited[i] = 0;
}
}
int sum(){
int sum = 1;
int pos = 1;
int temp = 1;
for (int i = 1; i < N; i++)
{
if(visited[i] == CONG){
sum += arr[i+1];
temp = 1;
pos = arr[i+1];
}
else if(visited[i] == TRU){
sum -= arr[i+1];
temp = -1;
pos = arr[i+1];
}
else{
sum = (sum+(-temp)*pos);
pos = pos*10+arr[i+1];
sum = sum +temp*pos;
}
}
return sum;
}
void BT(int vt){
if(vt == N){
if(sum() == 0){
cnt++;
}
return;
}
//cong
visited[vt] = CONG;
BT(vt+1);
visited[vt] = 0;
//tru
visited[vt] = TRU;
BT(vt+1);
visited[vt] = 0;
//gop
visited[vt] = GOP;
BT(vt+1);
visited[vt] = 0;
}
int convert(int st, int end){
int sum = 0;
for (int i = st; i <= end; i++)
{
sum = sum*10+i;
}
return sum;
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
arr_();
cnt = 0;
BT(1);
cout << "#" << test_case << " " << cnt << endl;
}
return 0;//Your program should return 0 on normal termination.
}
#crazy king
#include<iostream>
#define oo 9999999
using namespace std;
int N, M;
int arr[101][101];
int timeHorses[101][101];
int QHorses[100000][3];
int frontHorses, rearHorses;
int dxHorses[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dyHorses[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int numHorses;
int timeKing[101][101];
int QKing[100000][3];
int frontKing, rearKing;
int dxKing[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dyKing[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
enum{
POINT,
Z,
A,
B
};
void clear_time(){
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
timeHorses[i][j] = oo;
timeKing[i][j] = oo;
}
}
}
void bfs_time_horses(){
while(frontHorses < numHorses){
int row = QHorses[frontHorses][0];
int col = QHorses[frontHorses][1];
int time = QHorses[frontHorses++][2];
for (int i = 0; i < 8; i++)
{
int x = row+dxHorses[i];
int y = col+dyHorses[i];
if(x < 0 || x >= N || y < 0 || y >= M){
continue;
}
else{
if(arr[x][y] == POINT && timeHorses[x][y] == oo){
QHorses[rearHorses][0] = x;
QHorses[rearHorses][1] = y;
QHorses[rearHorses++][2] = time+1;
timeHorses[x][y] = time+1;
}
}
}
}
}
int bfs_tme_king(){
while(frontKing != rearKing){
int row = QKing[frontKing][0];
int col = QKing[frontKing][1];
int time = QKing[frontKing++][2];
for (int i = 0; i < 8; i++)
{
int x = row+dxKing[i];
int y = col+dyKing[i];
if(x < 0 || x >= N || y < 0 || y >= M){
continue;
}
else{
if(arr[x][y] == POINT && timeKing[x][y] == oo && timeHorses[x][y] == oo){
QKing[rearKing][0] = x;
QKing[rearKing][1] = y;
QKing[rearKing++][2] = time+1;
timeKing[x][y] = time+1;
}
if(arr[x][y] == B){
return time+1;
}
}
}
}
return -1;
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
char c;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> M >> N;
clear_time();
frontHorses = rearHorses = 0;
frontKing = rearKing = 0;
numHorses = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> c;
if(c=='.'){
arr[i][j] = POINT;
}
if(c == 'Z'){
arr[i][j] = Z;
timeHorses[i][j] = 0;
QHorses[rearHorses][0] = i;
QHorses[rearHorses][1] = j;
QHorses[rearHorses++][2] = 0;
numHorses++;
}
if(c == 'A'){
arr[i][j] = A;
timeKing[i][j] = 0;
QKing[rearKing][0] = i;
QKing[rearKing][1] = j;
QKing[rearKing++][2] = 0;
}
if(c == 'B'){
arr[i][j] = B;
}
}
}
bfs_time_horses();
int cnt = bfs_tme_king();
cout << cnt << endl;
}
return 0;
}
#dao cot
#include <iostream>
using namespace std;
// code 100/100
#include <stdio.h>
#define MAX_N 100
#define MAX_M 20
int rowValue[MAX_N];
int zeroCnt[MAX_N]; //Số ô "0" của hàng này
int duplicateCnt[MAX_N]; //Số dòng giống nhau
int valNum = 0;
int main() {
freopen("input.txt", "r", stdin);
int T;
int N, M, K;
cin >> T;
int tmpDigit, tmpVal, tmpCnt0;
int j;
for (int tc = 1; tc <= T; tc++) {
cin >> N >> M >> K;
valNum = 0;
for (int i = 0; i < N; i++) {
tmpVal = tmpCnt0 = 0;
for (j = 0; j < M; j++) {
cin>> tmpDigit;
tmpVal = (tmpVal << 1) | tmpDigit;
if (tmpDigit == 0) tmpCnt0++;
}
for (j = 0; j < valNum; j++) {
if (tmpVal == rowValue[j]) {// Có các hàng giống với hàng này, tăng số lượng trùng lặp
duplicateCnt[j]++;
break;
}
}
if (j == valNum) { //Không có hàng nào trùng với hàng này, tạo giá trị hàng mới
rowValue[valNum] = tmpVal;
zeroCnt[valNum] = tmpCnt0;
duplicateCnt[valNum++] = 1;
}
}
int Answer = 0;
for (j = 0; j < valNum; j++) {
if (zeroCnt[j] > K || (K - zeroCnt[j]) & 1) // Các hàng không thể thay đổi thành tất cả "1" trong K di chuyển
continue;
if (duplicateCnt[j] > Answer)
Answer = duplicateCnt[j];
}
cout <<"Case #" <<tc<<" "<< Answer << endl;
}
return 0;
}
#dimond
#include<iostream>
int N;
int arr[1001][1001];
int dsk[1001][1001];
int visited[1001];
int check;
using namespace std;
void clear(){
for (int i = 1; i <= N; i++)
{
visited[i] = 0;
}
}
void dfs(int dinh){
if(visited[dinh] == 2){
check = 1;
return;
}
for (int i = 1; i <= N; i++)
{
if(visited[dsk[dinh][i]] != 1 && dsk[dinh][i] != 0){
if(visited[dsk[dinh][i]] == 0){
visited[dsk[dinh][i]] = 1;
dfs(dsk[dinh][i]);
visited[dsk[dinh][i]] = 2;
}else dfs(dsk[dinh][i]);
}
if(dsk[dinh][i] == 0) break;
}
return;
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
int soLop;
int lop;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
dsk[i][j] = 0;
}
}
for (int i = 1; i <= N; i++)
{
cin >> soLop;
dsk[i][0] = soLop;
int index = 1;
for (int j = 1; j <= soLop; j++)
{
cin >> lop;
dsk[i][index++] = lop;
}
}
check = 0;
for (int i = 1; i <= N; i++)
{
clear();
dfs(i);
if(check == 1){
break;
}
}
if(check == 1)
cout << "Case #" << test_case << endl << "Yes" << endl;
else cout << "Case #" << test_case << endl << "No" << endl;
}
return 0;
}
#fast robot
#include<iostream>
#define oo 999999
//code 100/100
using namespace std;
int N, M;
int xStart, yStart, xEnd, yEnd;
int arr[201][201];
int visited[201][201];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int Q[50000][2];
int front , rear;
int cnt;
int tc;
int T;
int Answer;
char ch;
void clear_visited(){
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
visited[i][j] = oo;
}
}
}
int bfs(int row, int col){
front = rear = 0;
Q[rear][0] = row;
Q[rear++][1] = col;
visited[row][col] = cnt;
int tempx,tempy;
while(front != rear){
int r = Q[front][0];
int c = Q[front++][1];
for (int i = 0; i < 4; i++){
int x = r+dx[i];
int y = c+dy[i];
tempx=r;
tempy=c;
if(x < 0||x>=N||y<0||y>=M || visited[x][y]!=oo||arr[x][y] == 1) continue;
else{
if(visited[x][y] == oo && arr[x][y] == 0) cnt = visited[r][c]+1;
while(arr[tempx+dx[i]][tempy+dy[i]] == 0 && (tempx+dx[i]>=0 && tempx+dx[i] < N && tempy+dy[i] >= 0 && tempy+dy[i]<M)){
tempx += dx[i];
tempy += dy[i];
Q[rear][0] = tempx;
Q[rear++][1] = tempy;
visited[tempx][tempy] = cnt;
if(visited[xEnd-1][yEnd-1] != oo){
return visited[xEnd-1][yEnd-1];
}
}
}
}
}
return -1;
}
int main(){
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; ++tc){
cin >> M >> N;
cin >> yStart >> xStart >> yEnd >> xEnd;
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
cin >> ch;
arr[i][j] = ch-'0';
}
}
clear_visited();
cnt = -1;
cout << bfs(xStart-1, yStart-1) << endl;
}
return 0;
}
#path finding puzzles
#include<iostream>
#define oo 9999999
using namespace std;
int arr[201][201];
int visit[201][201];
int N, M, xStart, yStart, xEnd, yEnd;
int Q[400000][3];
int front, rear;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int bfs(int hang, int cot){
front = rear = 0;
Q[rear][0] = hang;
Q[rear][1] = cot;
Q[rear++][2] = 0;
visit[hang][cot] = 0;
while(front != rear){
int row = Q[front][0];
int col = Q[front][1];
int vs = Q[front++][2];
for (int i = 0; i < 4; i++)
{
int x = row+dx[i]*arr[row][col];
int y = col+dy[i]*arr[row][col];
if(x >= 0 && x < N && y >=0 && y < N && visit[x][y] == oo){
visit[x][y] = vs+1;
Q[rear][0] = x;
Q[rear][1] = y;
Q[rear++][2] = vs+1;
if(visit[N-1][N-1] != oo){
return vs+1;
}
}
}
}
return -1;
}
int main(){
int test_case;
int T;
int Answer;
int x, y;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> arr[i][j];
visit[i][j] = oo;
}
}
Answer = bfs(0, 0);
if(Answer == -1){
cout << "NO" << endl;
}
else cout << "YES" << endl;
}
return 0;
}
#quan tuong
#include<iostream>
#define oo 9999999
using namespace std;
int arr[201][201]; // mảng bàn cờ
int visit[201][201]; // mảng thăm
int N, M, xStart, yStart, xEnd, yEnd;
int Q[400000][3];
int front, rear;
int dx[4] = {-1, -1, 1, 1};
int dy[4] = {-1, 1, 1, -1};
int bfs(int hang, int cot){
front = rear = 0;
Q[rear][0] = hang;
Q[rear][1] = cot;
Q[rear++][2] = 0;
visit[hang][cot] = 0;
while(front != rear){
int row = Q[front][0];
int col = Q[front][1];
int vs = Q[front++][2];
for (int i = 0; i < 4; i++)
{
int x = row;
int y = col;
while(arr[x+dx[i]][y+dy[i]] != 1 && x+dx[i] >= 0 && x+dx[i] < N && y+dy[i] >=0 && y+dy[i] < N && visit[x+dx[i]][y+dy[i]] >= vs+1){
x = x+dx[i];
y = y+dy[i];
visit[x][y] = vs+1;
Q[rear][0] = x;
Q[rear][1] = y;
Q[rear++][2] = vs+1;
if(visit[xEnd-1][yEnd-1] != oo){
return vs+1;
}
}
}
}
return -1;
}
void clear_banco(){
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
arr[i][j] = 0;
visit[i][j] = oo;
}
}
}
int main(){
int test_case;
int T;
int Answer;
int x, y;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> N >> M >> xStart >> yStart >> xEnd >> yEnd;
clear_banco();
for (int i = 0; i < M; i++)
{
cin >> x >> y;
arr[x-1][y-1] = 1;
}
Answer = bfs(xStart-1, yStart-1);
cout << Answer << endl;
}
return 0;
}
#score
#include<iostream>
using namespace std;
int S, K, N;
int arr[21][21];
int visited[21][21];
int c;
void BT(int row, int col, int sum){
if(col == K-1){
if(sum == S){
c = c+1;
}
return;
}
if(sum > S){
return;
}
visited[row][col] = 1;
for (int i = 0; i < N; i++)
{
if(arr[i][col+1] >= arr[row][col] && visited[i][col+1] == 0){
BT(i, col+1, sum+arr[i][col+1]);
}
}
visited[row][col] = 0;
}
void clear_visited(){
for (int i = 0; i < N; i++)
{
for (int j = 0; j < K; j++)
{
visited[i][j] = 0;
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin >> S >> K >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < K; j++)
{
cin >> arr[i][j];
}
}
c = -1;
for (int i = 0; i < N; i++)
{
clear_visited();
BT(i, 0, arr[i][0]);
}
if(c != -1){
c = c+1;
}
cout << "Case " << test_case << endl << c << endl;
}
return 0;
}
#trade s6
#include<iostream>
using namespace std;
// code 100/100
int map[105][105];
int mapCopy[105][105];
int visit[105][105];
int Que[10000][2];
int n, ans, T;
int TS[6]; // mảng lưu tần số xuất hiện của các số
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1,0, 1,0 };
void reset() {
for (int i = 0; i < 6; i++) TS[i] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) visit[i][j] = 0;
}
}
void dfs(int x, int y, int oVal, int nVal) { // Tô màu cho cửa hàng
for (int h = 0; h < 4; h++) {
int nx = x + dx[h];
int ny = y + dy[h];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (!visit[nx][ny] && mapCopy[nx][ny] == oVal) {
visit[nx][ny] = 1;
mapCopy[nx][ny] = nVal;
dfs(nx, ny, oVal, nVal);
}
}
}
void bfs(int x, int y) {
reset();
visit[x][y] = 1;
int front = 0, rear = 0;
Que[rear][0] = x; // push vị trí đầu vào Queue
Que[rear++][1] = y;
while (front < rear) {
int r = Que[front][0]; // vị trí đang đứng
int c = Que[front++][1];
for (int h = 0; h < 4; h++) {
int nx = r + dx[h]; // vị trí sắp đến
int ny = c + dy[h];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // check vị trí sắp đến
if (!visit[nx][ny]) { // nếu vị trí sắp tới chưa được thăm
if ((map[r][c] == 0) || (map[nx][ny] == map[r][c])) {
TS[map[nx][ny]] ++; // Tăng tần số xuất hiện cho số đó
visit[nx][ny] = 1; // đánh dấu
Que[rear][0] = nx; // push số đó vào Queue
Que[rear++][1] = ny;
}
}
}
}
int maxTS = TS[1], color = 1;
for (int i = 2; i <= 5; i++)
if (TS[i] >= maxTS) { // Chọn ra số có tần số xuất hiện nhiều nhât
color = i;
maxTS = TS[i];
}
mapCopy[x][y] = color;
dfs(x, y, 0, color);
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mapCopy[i][j] == 0) {
bfs(i, j);
}
}
}
reset();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visit[i][j]) { // Tìm số vùng
ans++;
visit[i][j] = 1;
dfs(i, j, mapCopy[i][j], mapCopy[i][j]);
}
}
}
}
int main() {
freopen("input.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
mapCopy[i][j] = map[i][j];
}
}
ans = 0; solve();
cout << "Case #" << tc << endl << ans << endl;
}
return 0;
}
#battle city
#include<conio.h>
#include<iostream>
using namespace std;
//code 100/100
int tc, M, N, visited[301][301];
int QX[100001], QY[100001], head, tail;
char mt[301][301];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool isSafe(int x,int y){
if(x>=0 && x<M && y>=0 && y<N) return true;
else return false;
}
void bfs(int x, int y){
head=tail=-1;
visited[x][y]=1;
QX[++tail]=x; QY[tail]=y;
while(head!=tail){
x=QX[++head], y=QY[head];
for(int z=0;z<4;z++){
int nx=x+dx[z];
int ny=y+dy[z];
if(isSafe(nx,ny) && mt[nx][ny]=='B' && visited[nx][ny]>visited[x][y]+2){
QX[++tail]=nx; QY[tail]=ny;
visited[nx][ny]=visited[x][y]+2;
}
if(isSafe(nx,ny) && (mt[nx][ny]=='E' || mt[nx][ny]=='T') && visited[nx][ny]>visited[x][y]+1){
QX[++tail]=nx; QY[tail]=ny;
visited[nx][ny]=visited[x][y]+1;
}
}
}
}
int main(){
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
cin>>tc;
for(int t=1;t<=tc;t++){
cin>>M>>N;
cout<<"Case #"<<t<<endl;
int x_st,y_st,x_end,y_end;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
visited[i][j]=987654321;
cin>>mt[i][j];
if(mt[i][j]=='Y') {
x_st=i;y_st=j;
}
else if(mt[i][j]=='T'){
x_end=i;y_end=j;
}
}
}
int ans=0;
bfs(x_st,y_st);
ans=visited[x_end][y_end];
if(ans==987654321) cout<<-1<<endl;
else cout<<ans-1<<endl;
}
getch();
return 0;
}
#di an cuoi
#include<iostream>
// CODE 100/100
using namespace std;
int N, M;
int maTranKe[21][21];
int visited[21];
int cntMin;
void BT(int vt, int dich, int cnt){
if(vt == dich){
if(dich ==2)
BT(2, 1, cnt);
else{
if(cnt < cntMin){
cntMin = cnt;
}
}
return;
}
if(cnt > cntMin){
return;
}
for (int i = 1; i <= N ; i++)
{
if(maTranKe[vt][i] == 1){
if(dich == 2){
if(visited[i] == 0){
visited[i] = 1;
BT(i, dich, cnt+1);
visited[i] = 0;
}
}
if(dich == 1){
if(visited[i] != 2){
if(visited[i] == 0){
visited[i]++;
BT(i, dich, cnt+1);
visited[i]--;
}
else if(visited[i] == 1){
visited[i]++;
BT(i, dich, cnt);
visited[i]--;
}
}
}
}
}
}
void clear(){
for (int i = 1; i <= N; i++)
{
visited[i] = 0;
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
int Answer;
int u, v;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
cin >> N >> M;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
maTranKe[i][j] = 0;
}
}
for (int i = 0; i < M; i++)
{
cin >> u >> v;
maTranKe[u][v] = 1;
}
clear();
cntMin = 999999;
visited[1] = 1;
BT(1, 2, 1);
cout << cntMin << endl;
}
return 0;//Your program should return 0 on normal termination.
}
#cong chua
#include<iostream>
using namespace std;
int map[205][205];
int visit[205][205];
int queue[80000];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int n;
int x, y;
int front, rear;
void BFS(int x1, int y1){
front = rear = 0;
queue[rear++] = x1; // đẩy đỉnh xuất phát vào cuối queue
queue[rear++] = y1;
while(front < rear){
// cứ liên tục đi thăm bao giờ hết các đỉnh đầu queue rồi thôi
int r = queue[front++]; // lấy đỉnh đầu tiên của queue ra đi thăm
int c = queue[front++];
for (int i = 0; i < 4; i++) // bắt đầu thăm "4 lối đi"
{
int tmpRow = r + dx[i];
int tmpCol = c + dy[i];
if(tmpRow < 0 || tmpRow >=n || tmpCol <0 || tmpCol >= n) continue;
if(map[tmpRow][tmpCol] == 1 && visit[tmpRow][tmpCol] == 0){
visit[tmpRow][tmpCol] = visit[r][c] +1;
queue[rear++] = tmpRow; // nếu đỉnh thăm có "lối đi" thì đẩy "lối đi" vào cuối queue
queue[rear++] = tmpCol;
}
}
}
return;
}
int main(){
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
cin >> n;
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
{
cin >> map[r][c];
visit[r][c] = 0;
if(map[r][c] == 2){ // lưu vị trí công chúa
x = r;
y = c;
}
}
}
BFS(x, y);
if(visit[0][0] >0 && visit[n-1][n-1] >0){
cout << visit[0][0] + visit[n-1][n-1];
}
else{
cout << -1;
}
cout << endl;
}a
return 0;
}
#qua cau backtrack
#include<iostream>
// code mentor
using namespace std;
int n;
int arr[10000][5];
int maxP =0;
int isDone;
int dx[3] = {-1,0,1};
int dy[3] = {-1,-1,-1};
bool check(int x, int y){ // x là cột, y là hàng
if(x<0||x>=5|| y<0 ||y>=n){
return false;
}
return true;
}
void Try(int x,int y, int plank, int sum){
if(y==0){
if(sum>maxP){
maxP=sum;
}
isDone=true;
return;
}
for(int i=0;i<3;i++){
int tempx = x+dx[i];
int tempy= y+dy[i];
if(check(tempx, tempy)){
if(arr[tempy][tempx] != 2){
Try(tempx, tempy, plank, sum+arr[tempy][tempx]);
}
else{
if(plank){
Try(tempx, tempy,0, sum);
}
}
}
}
}
int main(){
//freopen("input.txt","r",stdin);
int test;
cin>>test;
for(int t=1;t<=test;t++){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<5;j++){
cin>>arr[i][j];
}
}
maxP=0;
isDone= false;
Try(2,n,1,0);
if(isDone){
cout<<"#"<< t<<" "<<maxP<<endl;
}
else{
cout<<"#"<< t<<" "<<-1<<endl;
}
}
return 0;
}
#suduku1
#include <iostream>
// code mentor 100
using namespace std;
bool isValidSudoku(char board[9][9]) {
bool rowUsed[9][9] = {false};
bool colUsed[9][9] = {false};
bool boxUsed[9][9] = {false};
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
continue;
int num = board[i][j] - '0'; // quy num từ 0 đến 8
int boxIndex = i /3*3+ j / 3; // công thức đánh chỉ số các ô 3*3
if (rowUsed[i][num] || colUsed[j][num] || boxUsed[boxIndex][num])
return false; // nếu cột đấy đã có số num rồi thì return false luôn
rowUsed[i][num] = true;
colUsed[j][num] = true;
boxUsed[boxIndex][num] = true;
}
}
return true;
}
int main() {
freopen("input.txt","r",stdin);
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++) {
char board[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin>>board[i][j];
}
}
bool isValid = isValidSudoku(board);
cout << "#" << tc << " " << (isValid ? "1" : "0") << endl;
}
return 0;
}
#output tuan trang mat
Case #1
27
Case #2
57
Case #3
58
Case #4
-1
Case #5
104
Case #6
4381981
Case #7
-1
Case #8
8882702
Case #9
10078253997
Case #10
11212103082
#pha huy he thong dien ver2
#include<iostream>
using namespace std;
int map[101][101];
int visited[101];
int n, front, rear;
int queue[10000001];
void BFS(int a){
front = rear = -1;
queue[++rear] = a;
visited[a] = 0;
while(front !=rear){
int x = queue[++front];
for(int i=0; i<n; i++){
if(map[x][i] ==1 && visited[i]==0){
visited[i] =1;
queue[++rear] = i;
}
}
}
}
int main(){
int t;
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>map[i][j];
}
}
int cnt =0;
for(int j=0; j<n; j++){
if(visited[j] == 0){
cnt++;
BFS(j);
}
}
int max1 =0;
for(int j=0; j<n; j++)visited[j] =0;
int res = -1;
for(int i=0; i<n; i++){
visited[i] =1;
int dem=0;
for(int j=0; j<n; j++){
if(visited[j] ==0){
dem++;
BFS(j);
}
}
if(dem>max1 && dem>cnt){
max1= dem;
res = i;
}
for(int j=0; j<n ;j++) visited[j] =0;
}
cout<<res+1<<endl;
}
return 0;
}
#hugo quang cao ver2
#include<iostream>
using namespace std;
int t, L[100], P[100], arrival[100], duration[100], n, max1 =0, visited[5], res[100][5];
void backtrack(int k, int t){
if(k==3){
int cnt =0;
for(int i=0; i<n; i++){
int a=0;
for(int j=2; j>=0; j--){
if(res[i][j]!=0 && P[j] >a){
a = P[j];
}
}
cnt +=a;
}
if(cnt> max1) max1= cnt;
return;
}
if(t>=50) return;
for(int i=0;i<3; i++){
if(visited[i] ==0){
visited[i]=1;
for(int j=t; j<50; j++){
for(int h=0; h<n; h++){
if(arrival[h] <=j && j + L[i] <= arrival[h] + duration[h]){
res[h][i] = 1;
}
}
backtrack(k+1, j+ L[i]);
for(int h=0; h<n; h++){
if(arrival[h] <=j && j + L[i] <= arrival[h] + duration[h]){
res[h][i] = 0;
}
}
}
visited[i] =0;
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin>>t;
for(int tc=1; tc<=t; tc++){
cin>>n;
for(int i=0; i<3; i++) cin>>L[i];
for(int i=0; i<3; i++) cin>>P[i];
for(int i=0; i<n; i++){
cin>>arrival[i];
cin>>duration[i];
res[i][0] = res[i][1] = res[i][2] =0;
}
max1 =0;
backtrack(0, 1);
cout<<"Case #"<<tc<<endl;
cout<<max1<<endl;
}
return 0;
}Editor is loading...
Leave a Comment