P15621求调(DFS)

[栗子酱 (栗栗子)]

题目：

我代码：

#include <bits/stdc++.h>
using namespace std;
int n,sx,sy,ex,ey,minn=2147483647;
bool vis[110][110];
int dx[]={-2,-1,1,2};
int dy[]={1,2,2,1};
void dfs(int x,int y,int num)
{
	if(x==ex && y==ey)
	{
		if(num<minn)
		{
			minn=num;
		}
		return;
	}
	for(int i=0;i<=3;i++)
	{
		if(x+dx[i]>n || x+dx[i]<1 || y+dy[i]>n || y+dy[i]<1 || x+dx[i]>ex || y+dy[i]>ey || !vis[x+dx[i]][y+dy[i]])
		{
			continue;
		}
		vis[x+dx[i]][y+dx[i]]=true;
		dfs(x+dx[i],y+dy[i],num+1);
		vis[x+dx[i]][y+dx[i]]=false;
	}
}
int main()
{
	cin>>n>>sx>>sy>>ex>>ey;
	dfs(sx,sy,0);
	cout<<minn;
	return 0;
}

[徐昊轩]

一道题，求解 求调

[徐昊轩]

你这个马的dxdy怎么只有4个，应该有8个

[栗子酱 (栗栗子)]

@徐昊轩

dxdy怎么只有4个，应该有8

《不回头》

[徐昊轩]

你加上试试嘛，还有帮我调一下

[栗子酱 (栗栗子)]

不好使，我试过了。。。

[徐昊轩]

@栗子酱

#include <bits/stdc++.h>
using namespace std;
int n,sx,sy,ex,ey,minn=2147483647;
bool vis[110][110];
int dx[]={-2,-1,1,2};
int dy[]={1,2,2,1};
void dfs(int x,int y,int num)
{
	if(x==ex && y==ey)
	{
		if(num<minn)
		{
			minn=num;
		}
		return;
	}
	for(int i=0;i<=3;i++)
	{
		if(x+dx[i]>n || x+dx[i]<1 || y+dy[i]>n || y+dy[i]<1 || x+dx[i]>ex || y+dy[i]>ey || !vis[x+dx[i]][y+dy[i]])
		{
			continue;
		}
		vis[x+dx[i]][y+dx[i]]=true;
		dfs(x+dx[i],y+dy[i],num+1);
		vis[x+dx[i]][y+dx[i]]=false;
	}
}
int main()
{
	cin>>n>>sx>>sy>>ex>>ey;
	dfs(sx,sy,0);
	cout<<minn;
	return 0;
}

vis要初始化？

[栗子酱 (栗栗子)]

默认为0，走过为1。。。@李铭浩 @tyx 帮帮我

[栗子酱 (栗栗子)]

@Syxqwq

[Syxqwq (Loser_Syx)]

？？？

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

不是，我给你们看个图：
这是回头的：

这是不回头的：

非常迷惑

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

他们俩的数据点是互补的

[Syxqwq (Loser_Syx)]

你的马 咋只能有 4 种跳法

正常马 是 8 种

[栗子酱 (栗栗子)]

图一怎么用max

[栗子酱 (栗栗子)]

他不是最小么

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

min也是70分

[tyx (༺༺■̵̶̸̸̴̴̷̩͎̬͍̙͎͕͎̩͍͇̜͍̯̖͎̙͓̪͎͓̜̟͖͈̩͈̜̮̝̠̫̠͉̘̳̳̦͈͇̖͓̩͙̩̤͇̠̠̣͔͕̲͍̪̮̥̗̦͍͇͍͖̟͔͔̲̜̗̱̤̲̤̱̝̟͇̖͔̮͙̣͚̗̣̤̱͇͖̪͚͉̜̫̤̮͎̖̥͙̜̖̞̥͔͍̳͙̉̃̀͑͗͋̾̔̓̄̆̐̾͊̐̀̆̆̋̎̂̓̈̆̑͋͛̐̍̾̎͐̈́͋̌̾̓̌̂̿͗̂̂͗̊̇͛̾̋͂͒̉̿̾̽͛̈́̍̋͗̐͒͂̊̾͒̃̎̇͐̎̇́̅̈́͂̋̑͒́̓͆̅̓͌͗͋̏͒̽̒̉̂̔̒͆̊̐̀̈́̀͒̽̚̚ͅͅ҉再见，匹诺康尼_C++CodeIkun༻༻)]

[栗子酱 (栗栗子)]

RE了，6

#include <bits/stdc++.h>
using namespace std;
int n,sx,sy,ex,ey,minn=2147483647;
int dx[]={-2,-2,-1,1,-1,2,2};
int dy[]={-1,1,-2,2,2,-1,1};
bool vis[510][510];
struct str{
	int x,y,num;
};
queue <str> q;
void bfs(){
	str tmp;
	tmp.num=0,tmp.x=sx,tmp.y=sy;
	q.push(tmp);
	vis[sx][sy]=true;
	while(!q.empty()){
		tmp=q.front();
		if(tmp.x==ex && tmp.y==ey){
			if(tmp.num<minn){
				minn=tmp.num;
			}
		}
		q.pop();
		for(int i=1;i<=7;i++){
			int nowx=tmp.x+dx[i];
			int nowy=tmp.y+dy[i];
			if(nowx>=1 && nowy>=1 && nowx<=n && nowy<=n && !vis[nowx][nowy])
			{
				vis[nowx][nowy]=true;
				str tmp2;
				tmp2.x=nowx;
				tmp2.y=nowy;
				tmp2.num=tmp.num+1;
				q.push(tmp2);
			}
		}
	}
	if(minn==2147483647){
		cout<<-1;
	}
	else{
		cout<<minn;
	}
}
int main()
{
	cin>>n>>sx>>sy>>ex>>ey;
	bfs();
	return 0;
}

[anon86415901]

为啥只有7种走法

???

[栗子酱 (栗栗子)]

改完真的只有70分！！！

#include <bits/stdc++.h>
using namespace std;
long long n,sx,sy,ex,ey,minn=2147483647;
long long dx[]={-2,-2,-1,1,-1,1,2,2};
long long dy[]={-1,1,-2,-2,2,2,-1,1};
bool vis[510][510];
struct str{
	long long x,y,num;
};
queue <str> q;
void bfs(){
	str tmp;
	tmp.num=0,tmp.x=sx,tmp.y=sy;
	q.push(tmp);
	vis[sx][sy]=true;
	while(!q.empty()){
		tmp=q.front();
		if(tmp.x==ex && tmp.y==ey){
			if(tmp.num<minn){
				minn=tmp.num;
			}
		}
		q.pop();
		for(long long i=0;i<8;i++){
			long long nowx=tmp.x+dx[i];
			long long nowy=tmp.y+dy[i];
			if(nowx>=1 && nowy>=1 && nowx<=n && nowy<=n && !vis[nowx][nowy])
			{
				vis[nowx][nowy]=true;
				str tmp2;
				tmp2.x=nowx;
				tmp2.y=nowy;
				tmp2.num=tmp.num+1;
				q.push(tmp2);
			}
		}
	}
	if(minn==2147483647){
		cout<<-1;
	}
	else{
		cout<<minn;
	}
}
int main()
{
	cin>>n>>sx>>sy>>ex>>ey;
	bfs();
	return 0;
}