Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

, 这是生成小范围数据的代码:

Posted by wm3418925 at 2015-08-26 19:50:35 on Problem 1915 and last updated at 2015-08-26 19:56:02
In Reply To:共享代码. 小范围内的查表, 大范围接近小范围, 0MS Posted by:wm3418925 at 2015-08-26 19:48:59

#include<iostream>
#include<queue>
using namespace std;
#include<memory.h>

#define maxn 12
#define max_distance 3

struct node
{
	int x,y;
	int step;
};

bool vis[maxn][maxn];

int start_x,start_y;
int end_x,end_y;
int l;


int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};



int my_abs(int a)
{
	if (a>=0) return a;
	return -a;
}
int my_min(int a, int b)
{
	if (a<b) return a;
	return b;
}
int my_max(int a, int b)
{
	if (a>b) return a;
	return b;
}

int bfs()
{
	int d;
	memset(vis,false,sizeof(vis));
	queue<node>q;
	node cur,next;
	cur.x = start_x;
	cur.y = start_y;
	cur.step = 0;
	q.push(cur);
	vis[start_x][start_y] = true;

	while(!q.empty())
	{
		cur = q.front();
		q.pop();
		if(cur.x == end_x && cur.y == end_y)
			return cur.step;
		for(d = 0; d < 8;d++)
		{
			next.x = cur.x + dir[d][0];
			next.y = cur.y + dir[d][1];
			if(next.x >= 0 && next.y >= 0 && next.x <= l-1 && next.y <= l-1 && !vis[next.x][next.y])
			{
				next.step = cur.step + 1;
				if(end_x == next.x && end_y == next.y)
					return next.step;
				vis[next.x][next.y] = true;
				q.push(next);
			}
		}
	}
	return -1;
}




static char dfs1[1][1];
static char dfs2[4][4];
static char dfs3[9][9];
static char dfs4[16][16];
static char dfs5[25][25];
static char dfs6[36][36];
static char dfs7[49][49];
static char dfs8[64][64];
static char dfs9[81][81];
static char dfs10[100][100];
static char dfs11[121][121];
static char dfs12[144][144];
static char * dfss[12] = 
{
	(char *) dfs1,
	(char *) dfs2,
	(char *) dfs3,
	(char *) dfs4,
	(char *) dfs5,
	(char *) dfs6,
	(char *) dfs7,
	(char *) dfs8,
	(char *) dfs9,
	(char *) dfs10,
	(char *) dfs11,
	(char *) dfs12,
};
static char get_my_dfs(int ll, int i, int j, int ii, int jj)
{
	int ll2 = ll*ll;
	int ll3 = ll2*ll;
	return dfss[ll-1][i*ll3+j*ll2 + ii*ll+jj];
}
static void set_my_dfs(int ll, int i, int j, int ii, int jj, char value)
{
	int ll2 = ll*ll;
	int ll3 = ll2*ll;
	dfss[ll-1][i*ll3+j*ll2 + ii*ll+jj] = value;
}

/*int main()
{
	int step0, step1;
	int i,j,ii,jj;

	FILE * fp = fopen("data.txt", "w");
	for(l=1; l <= maxn; l++)
	{
		printf("l=%d\n", l);
		for(i=0; i<l; ++i)for(j=0; j<l; ++j)for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
		{
			start_x = i;
			start_y = j;
			
			end_x = ii;
			end_y = jj;
			
			
			step1 = bfs();
			if (step1 < 0) step1 = 0;
			
			set_my_dfs(l, i, j, ii, jj, (char)step1);
		}

		fprintf(fp, "\n\nstatic const char * dfs%d[%d] = \n{\n", l, l*l);
		for(i=0; i<l; ++i)for(j=0; j<l; ++j)
		{
			fputc('"', fp);
			int count=0;
			for(ii=i; ii<l; ++ii)for(jj=0; jj<l; ++jj)
			{
				step1 = get_my_dfs(l, i, j, ii, jj);
				
				if (count & 1)
				{
					int ccc = step0*9 + step1 + 35;
					if (ccc == '\\') fputc('\\', fp);
					fputc(ccc, fp);
				}
				else
				{
					step0 = step1;
				}

				++count;
			}
			if (count & 1)
			{
				int ccc = step0*9 + 35;
				if (ccc == '\\') fputc('\\', fp);
				fputc(ccc, fp);
			}
			fputs("\",\n", fp);
		}
		fputs("};\n\n", fp);
	}
	fclose(fp);
	
	return 0;
}*/

/*int main()
{
	int step0, step1;
	int i,j,ii,jj;
	
	FILE * fp = fopen("helf.txt", "w");
	for(l=1; l <= maxn; l++)
	{
		printf("l=%d\n", l);
		for(i=0; i<l; ++i)for(j=0; j<l; ++j)for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
		{
			start_x = i;
			start_y = j;
			
			end_x = ii;
			end_y = jj;
			
			
			step1 = bfs();
			if (step1 < 0) step1 = 0;
			
			set_my_dfs(l, i, j, ii, jj, (char)step1);
		}
		
		fprintf(fp, "\n\nstatic const char * dfs%d[%d] = \n{\n", l, l*l);
		for(i=0; i<l; ++i)for(j=0; j<l; ++j)
		{
			fputc('"', fp);

			for(ii=i; ii<l; ++ii)for(jj=0; jj<l; ++jj)
			{
				step1 = get_my_dfs(l, i, j, ii, jj);
				
				fputc(step1+'0', fp);
			}
			fputs("\",\n", fp);
		}
		fputs("};\n\n", fp);
	}

	fclose(fp);
	
	return 0;
}*/

int main()
{
	int step;
	int i,j,ii,jj;
	
	FILE * fp = fopen("full.txt", "w");
	for(l=1; l <= maxn; l++)
	{
		printf("l=%d\n", l);
		for(i=0; i<l; ++i)for(j=0; j<l; ++j)for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
		{
			start_x = i;
			start_y = j;
			
			end_x = ii;
			end_y = jj;
			
			
			step = bfs();
			if (step < 0) step = 0;
			
			set_my_dfs(l, i, j, ii, jj, (char)step);
		}
		
		fprintf(fp, "\n\nstatic const char * dfs%d[%d] = \n{\n", l, l*l);
		for(i=0; i<l; ++i)for(j=0; j<l; ++j)
		{
			fputc('"', fp);
			
			for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
			{
				step = get_my_dfs(l, i, j, ii, jj);
				
				fputc(step+'0', fp);
			}
			fputs("\",\n", fp);
		}
		fputs("};\n\n", fp);
	}
	
	fclose(fp);
	
	return 0;
}

Followed by:

我这个算法, 期盼宽度l 可以非常大, 算法时间不会提高 (0) wm3418925 2015-08-27 10:21:00

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<iostream>
> #include<queue>
> using namespace std;
> #include<memory.h>
> 
> #define maxn 12
> #define max_distance 3
> 
> struct node
> {
> 	int x,y;
> 	int step;
> };
> 
> bool vis[maxn][maxn];
> 
> int start_x,start_y;
> int end_x,end_y;
> int l;
> 
> 
> int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};
> 
> 
> 
> int my_abs(int a)
> {
> 	if (a>=0) return a;
> 	return -a;
> }
> int my_min(int a, int b)
> {
> 	if (a<b) return a;
> 	return b;
> }
> int my_max(int a, int b)
> {
> 	if (a>b) return a;
> 	return b;
> }
> 
> int bfs()
> {
> 	int d;
> 	memset(vis,false,sizeof(vis));
> 	queue<node>q;
> 	node cur,next;
> 	cur.x = start_x;
> 	cur.y = start_y;
> 	cur.step = 0;
> 	q.push(cur);
> 	vis[start_x][start_y] = true;
> 
> 	while(!q.empty())
> 	{
> 		cur = q.front();
> 		q.pop();
> 		if(cur.x == end_x && cur.y == end_y)
> 			return cur.step;
> 		for(d = 0; d < 8;d++)
> 		{
> 			next.x = cur.x + dir[d][0];
> 			next.y = cur.y + dir[d][1];
> 			if(next.x >= 0 && next.y >= 0 && next.x <= l-1 && next.y <= l-1 && !vis[next.x][next.y])
> 			{
> 				next.step = cur.step + 1;
> 				if(end_x == next.x && end_y == next.y)
> 					return next.step;
> 				vis[next.x][next.y] = true;
> 				q.push(next);
> 			}
> 		}
> 	}
> 	return -1;
> }
> 
> 
> 
> 
> static char dfs1[1][1];
> static char dfs2[4][4];
> static char dfs3[9][9];
> static char dfs4[16][16];
> static char dfs5[25][25];
> static char dfs6[36][36];
> static char dfs7[49][49];
> static char dfs8[64][64];
> static char dfs9[81][81];
> static char dfs10[100][100];
> static char dfs11[121][121];
> static char dfs12[144][144];
> static char * dfss[12] = 
> {
> 	(char *) dfs1,
> 	(char *) dfs2,
> 	(char *) dfs3,
> 	(char *) dfs4,
> 	(char *) dfs5,
> 	(char *) dfs6,
> 	(char *) dfs7,
> 	(char *) dfs8,
> 	(char *) dfs9,
> 	(char *) dfs10,
> 	(char *) dfs11,
> 	(char *) dfs12,
> };
> static char get_my_dfs(int ll, int i, int j, int ii, int jj)
> {
> 	int ll2 = ll*ll;
> 	int ll3 = ll2*ll;
> 	return dfss[ll-1][i*ll3+j*ll2 + ii*ll+jj];
> }
> static void set_my_dfs(int ll, int i, int j, int ii, int jj, char value)
> {
> 	int ll2 = ll*ll;
> 	int ll3 = ll2*ll;
> 	dfss[ll-1][i*ll3+j*ll2 + ii*ll+jj] = value;
> }
> 
> /*int main()
> {
> 	int step0, step1;
> 	int i,j,ii,jj;
> 
> 	FILE * fp = fopen("data.txt", "w");
> 	for(l=1; l <= maxn; l++)
> 	{
> 		printf("l=%d\n", l);
> 		for(i=0; i<l; ++i)for(j=0; j<l; ++j)for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
> 		{
> 			start_x = i;
> 			start_y = j;
> 			
> 			end_x = ii;
> 			end_y = jj;
> 			
> 			
> 			step1 = bfs();
> 			if (step1 < 0) step1 = 0;
> 			
> 			set_my_dfs(l, i, j, ii, jj, (char)step1);
> 		}
> 
> 		fprintf(fp, "\n\nstatic const char * dfs%d[%d] = \n{\n", l, l*l);
> 		for(i=0; i<l; ++i)for(j=0; j<l; ++j)
> 		{
> 			fputc('"', fp);
> 			int count=0;
> 			for(ii=i; ii<l; ++ii)for(jj=0; jj<l; ++jj)
> 			{
> 				step1 = get_my_dfs(l, i, j, ii, jj);
> 				
> 				if (count & 1)
> 				{
> 					int ccc = step0*9 + step1 + 35;
> 					if (ccc == '\\') fputc('\\', fp);
> 					fputc(ccc, fp);
> 				}
> 				else
> 				{
> 					step0 = step1;
> 				}
> 
> 				++count;
> 			}
> 			if (count & 1)
> 			{
> 				int ccc = step0*9 + 35;
> 				if (ccc == '\\') fputc('\\', fp);
> 				fputc(ccc, fp);
> 			}
> 			fputs("\",\n", fp);
> 		}
> 		fputs("};\n\n", fp);
> 	}
> 	fclose(fp);
> 	
> 	return 0;
> }*/
> 
> /*int main()
> {
> 	int step0, step1;
> 	int i,j,ii,jj;
> 	
> 	FILE * fp = fopen("helf.txt", "w");
> 	for(l=1; l <= maxn; l++)
> 	{
> 		printf("l=%d\n", l);
> 		for(i=0; i<l; ++i)for(j=0; j<l; ++j)for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
> 		{
> 			start_x = i;
> 			start_y = j;
> 			
> 			end_x = ii;
> 			end_y = jj;
> 			
> 			
> 			step1 = bfs();
> 			if (step1 < 0) step1 = 0;
> 			
> 			set_my_dfs(l, i, j, ii, jj, (char)step1);
> 		}
> 		
> 		fprintf(fp, "\n\nstatic const char * dfs%d[%d] = \n{\n", l, l*l);
> 		for(i=0; i<l; ++i)for(j=0; j<l; ++j)
> 		{
> 			fputc('"', fp);
> 
> 			for(ii=i; ii<l; ++ii)for(jj=0; jj<l; ++jj)
> 			{
> 				step1 = get_my_dfs(l, i, j, ii, jj);
> 				
> 				fputc(step1+'0', fp);
> 			}
> 			fputs("\",\n", fp);
> 		}
> 		fputs("};\n\n", fp);
> 	}
> 
> 	fclose(fp);
> 	
> 	return 0;
> }*/
> 
> int main()
> {
> 	int step;
> 	int i,j,ii,jj;
> 	
> 	FILE * fp = fopen("full.txt", "w");
> 	for(l=1; l <= maxn; l++)
> 	{
> 		printf("l=%d\n", l);
> 		for(i=0; i<l; ++i)for(j=0; j<l; ++j)for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
> 		{
> 			start_x = i;
> 			start_y = j;
> 			
> 			end_x = ii;
> 			end_y = jj;
> 			
> 			
> 			step = bfs();
> 			if (step < 0) step = 0;
> 			
> 			set_my_dfs(l, i, j, ii, jj, (char)step);
> 		}
> 		
> 		fprintf(fp, "\n\nstatic const char * dfs%d[%d] = \n{\n", l, l*l);
> 		for(i=0; i<l; ++i)for(j=0; j<l; ++j)
> 		{
> 			fputc('"', fp);
> 			
> 			for(ii=0; ii<l; ++ii)for(jj=0; jj<l; ++jj)
> 			{
> 				step = get_my_dfs(l, i, j, ii, jj);
> 				
> 				fputc(step+'0', fp);
> 			}
> 			fputs("\",\n", fp);
> 		}
> 		fputs("};\n\n", fp);
> 	}
> 	
> 	fclose(fp);
> 	
> 	return 0;
> }

Home Page Go Back To top