爆弾問題C++

32565 ワード

自分で地図と爆弾の初期位置を指定して、爆弾の位置は移動することができて、今あなたは爆弾を移動して爆弾を最も多くの敵を爆破することができて、爆弾は一度に1行と1列を爆破することができますが、壁は爆弾を遮ることができます.与えられた地図の中で#は壁を表し、Gは敵を表す.爆弾が移動できる場所を代表し、結果が唯一であることを保証します.このテーマでは、爆弾の位置は移動できますが、すべての位置爆弾が到着できるわけではありません.爆弾は初期位置の場合、移動可能な位置に沿って移動できるだけです.
以下は道を探す関数(i,jは爆弾の初期位置)
int getnum(int i, int j) {
     
	int num, x, y;
	sum = 0;//sum    (        ),        0
	//   i,j        x,y ,         4             

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (x < 0)//      
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		x--;//          
	}

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (x > n)//      
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		x++;//          
	}

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (y < 0)//      
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		if(y>0)
		y--;//          
	}

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (y > m)//      
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		y++;//          
	}

	return sum;//     
}


以下はすべてのコードです
#include
using namespace std;
struct note {
     
	int x;//   
	int y;//   
};
char a[21][21];//      
int i, j, k, sum, Max = 0, mx, my, n, m, startx, starty, tx, ty;

int getnum(int i, int j) 
{
     
	int num, x, y;
	sum = 0;//sum    (        ),        0
	//   i,j        x,y ,         4             

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (x < 0)
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		x--;//          
	}

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (x > n)
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		x++;//          
	}

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (y < 0)
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		if(y>0)
		y--;//          
	}

	//            
	x = i; y = j;
	while (a[x][y] != '#') {
     //        ,        
		//         ,     
		if (y > m)
			break;
		if (a[x][y] == 'G') {
     
			sum++;
		}
		y++;//          
	}

	return sum;//     
}

int main() 
{
     
	struct note que[401];//         20*20,          400 
	int head, tail;//  
	int book[21][21] = {
      0 };//               0 


	//                
	int next[4][2] = {
      {
     0,1},//   
					{
     1,0},//   
					{
     0,-1},//    
					{
     -1,0}//   	
	};//4 2      

	cout << "   n m,n  ,m  :" << endl;
	cin >> n >> m;
	//      
	cout << "       :" << endl;
	cin >> startx >> starty;

	//    
	cout << "       :" << endl;
	for (i = 1; i <= n; i++) 
	{
     
		for (j = 1; j <= m; j++) {
     
			cin >> a[i][j];
		}
	}

	//     
	head = tail = 1;
	//             
	que[tail].x = startx;
	que[tail].y = starty;
	tail++;
	book[startx][starty] = 1;
	if ( a[startx][starty] =='#'|| a[startx][starty] == 'G'  )
	{
     
		cout << "    ";//          
		return 0;
	}
	Max = getnum(startx, starty);
	mx = startx;
	my = starty;

	//         
	while (head < tail) 
	{
     
		//  4   
		for (k = 0; k <= 3; k++) 
		{
     
			//           
			tx = que[head].x + next[k][0];
			ty = que[head].y + next[k][1];
			/*
			next    
			next[0][0]=0;	next[0][1]=1;   //   
			next[1][0]=1;	next[1][1]=0;   //   
			next[2][0]=0;	next[2][1]=-1;  //   
			next[3][0]=-1;	next[3][1]=0;	//   

			*/
			//      
			if (tx<1 || tx>n || ty<1 || ty>m)
			{
     
				continue;//       
			}

			//                
			if (a[tx][ty] == '.' && book[tx][ty] == 0) 
			{
     
				
				book[tx][ty] = 1;//        ,              
				//            
				que[tail].x = tx;
				que[tail].y = ty;
				tail++;

				//                  
				sum = getnum(tx, ty);
				//  Max  
				if (sum > Max) 
				{
     
					//                Max,   Max,  Max my      
					Max = sum;
					mx = tx;
					my = ty;
				}
			}
		}
		head++;//           ,         ,head++             

	}

	//                   
	cout << endl << "      (" << mx << "," << my << ")     " << Max << "   ";

	getchar();
	return 0;
}