CDOJ 1134 남신의 데이트

1572 단어 동적 기획CDOJ
범위가 좁아서 상압하면 돼요. T 못해요.
BFS 큐는 동일한 방식으로 작동합니다.
코드:
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 99999999
int pow_2[10];
int grid[10][10];
int dp[1024][10][10];
int main()
{
	//freopen("input.txt", "r", stdin);
	pow_2[0] = 1;
	for (int i = 1; i < 10; ++i)
		pow_2[i] = pow_2[i - 1] << 1;
	for (int i = 0; i < 10; ++i)
		for (int j = 0; j < 10; ++j)
			for (int k = 0; k < 1024; ++k)
				dp[k][i][j] = INF;
	for (int i = 0; i < 10; ++i)
		for (int j = 0; j < 10; ++j)
			scanf("%d", &grid[i][j]);
	dp[pow_2[grid[0][0]]][0][0] = grid[0][0];
	int x = pow_2[grid[0][0]], y = pow_2[grid[0][0]];
	for (int i = 1; i < 10; ++i)
	{
		dp[x | pow_2[grid[i][0]]][i][0] = dp[x][i - 1][0] + grid[i][0];
		x |= pow_2[grid[i][0]];
		dp[y | pow_2[grid[0][i]]][0][i] = dp[y][0][i - 1] + grid[0][i];
		y |= pow_2[grid[0][i]];
	}
	for (int i = 1; i < 10; ++i)
		for (int j = 1; j < 10; ++j)
			for (int k = 0; k < 1024; ++k)
			{
				if (dp[k][i - 1][j]!=INF)
					dp[k | pow_2[grid[i][j]]][i][j] = min(dp[k][i - 1][j] + grid[i][j], dp[k | pow_2[grid[i][j]]][i][j]);
				if (dp[k][i][j - 1] != INF)
					dp[k | pow_2[grid[i][j]]][i][j] = min(dp[k][i][j - 1] + grid[i][j], dp[k | pow_2[grid[i][j]]][i][j]);
			}
	printf("%d
", dp[1023][9][9]); //system("pause"); //while (1); return 0; }

좋은 웹페이지 즐겨찾기